hdu 4441-白红宇

hdu 4441

阅读量：4686 次

发布时间：2019-06-09

本文共 5943 字，大约阅读时间需要 19 分钟。

insert p:

　　　　在p+1的位置插入v，然后 v前面的正数的个数= -v前面的负数的个数，这样找到的位置就是 -v的插入位置

remove v: 因为可以记录每个v的节点标号，所以直接操作。

query v:同remove。

开始时，用优先队列来维护当前最小的v值，TLE。然后用线段树模拟了一个（本来应该是堆的）优先队列。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #define KT ch[ch[root][1]][0]  7 #define LC ch[x][0]  8 #define RC ch[x][1]  9 #define N 210001 10 #define lson l,mid,rt<<1|1 11 #define rson mid+1,r,rt<<1 12 #define Root 1,n,1 13 using namespace std; 14  15 typedef long long LL; 16 struct xds{ 17     int a[N<<2]; 18     int n; 19     void init(int nn){ 20         n=nn; 21         build(Root); 22     } 23     void pushup(int rt){ 24         if(a[rt<<1|1]==-1){ 25             a[rt]=a[rt<<1]; 26         } 27         else{ 28             a[rt]=a[rt<<1|1]; 29         } 30     } 31     void build(int l,int r,int rt){ 32         if(l==r){ 33             a[rt]=l; 34             return; 35         } 36         int mid=(l+r)>>1; 37         build(lson); 38         build(rson); 39         pushup(rt); 40     } 41  42     void updata(int x,int f,int l,int r,int rt){ 43         if(l==r){ 44             if(f) a[rt]=-1; 45             else a[rt]=l; 46             return; 47         } 48         int mid=(l+r)>>1; 49         if(x<=mid)updata(x,f,lson); 50         else updata(x,f,rson); 51         pushup(rt); 52     } 53     int query(int L,int R,int l,int r,int rt){ 54         if(L<=l&&r<=R){ 55             return a[rt]; 56         } 57         int mid=(l+r)>>1; 58         int ans=query(L,R,lson); 59         if(ans!=-1)return ans; 60         return query(L,R,rson); 61     } 62     void push(int val){ 63         updata(val,0,Root); 64     } 65     int top(){ 66         return query(1,n,Root); 67     } 68     void pop(){ 69         updata(top(),1,Root); 70     } 71 }Q; 72 struct SplayTree{ 73     int root; 74     int fa[N]; 75     int ch[N][2]; 76     int sz[N]; 77     int top1; 78     int top2; 79     int ss[N]; 80     int que[N]; 81  82     void pushdown(int x){ 83  84     } 85     void pushup(int x){ 86         sz[x]=1+sz[LC]+sz[RC]; 87  88         sum[x]=val[x]+sum[LC]+sum[RC]; 89         neg[x]=(val[x]<0) + neg[LC]+neg[RC]; 90     } 91     void rotate(int x,bool f){ 92         int y=fa[x]; 93         int z=fa[y]; 94         pushdown(y); 95         pushdown(x); 96         ch[y][!f]=ch[x][f]; 97         fa[ch[x][f]]=y; 98         fa[x]=z; 99         if (z) {100             ch[z][ch[z][1]==y] = x;101         }102         ch[x][f] = y;103         fa[y]=x;104         pushup(y);105     }106     void splay(int x, int g) {107         int y = fa[x];108         pushdown(x);109         while(y!=g){110             int z= fa[y];111             bool f = (ch[y][0]==x);112             if(z != g && f == (ch[z][0]==y)){113                 rotate(y,f);114             }115             rotate(x,f);116             y=fa[x];117         }118         pushup(x);119         if(g==0) root = x;120     }121     void rotateTo(int k,int g) {122         int x=root;123         pushdown(x);124         while(sz[LC] != k){125             if(k
           
            r){137 return ;138 }139 int x = (l + r) >> 1;140 LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0;141 RC = (r >= x + 1)? (x + 1 + r)>> 1 :0;142 fa[x] = f;143 build(l,x - 1,x);144 build(x + 1,r,x);145 pushup(x);146 }147 void erase(int x){148 if(x==0)149 return;150 int father= fa[x];151 int head = 0, tail=0;152 for(que[tail++] =x ; head < tail; head++){153 ss[top2++] = que[head];154 if(ch[que[head]][0]){155 que[tail++]=ch[que[head]][0];156 }157 if(ch[que[head]][1]){158 que[tail++] = ch[que[head]][1];159 }160 }161 ch[father][ch[father][1]==x]=0;162 pushup(father);163 }164 void treaval(int x){165 if (x) {166 pushdown(x);167 treaval(LC);168 printf("@%d",val[x]);169 170 treaval(RC);171 }172 }173 int idx(int v){174 if(v==0)return 0;175 if(v>0)return v;176 else177 return -v+N;178 }179 void newNode(int &x,int c){180 if(top2){181 x = ss[--top2];182 } else {183 x = ++top1;184 }185 LC = RC = fa[x] =0;186 sz[x] = 1;187 val[x] = c;188 sum[x] = c;189 neg[x] = (c<0);190 pos[idx(c)]=x;191 }192 void makeTree(int &x, int l, int r, int f){193 if(l > r){194 return;195 }196 int m=(l+r)>>1;197 newNode(x, num[m]);198 makeTree(LC,l,m-1,x);199 makeTree(RC,m+1,r,x);200 fa[x]=f;201 pushup(x);202 }203 void debug(){204 treaval(root);205 cout<
            
             k){232 return find(LC,k);233 }else{234 return find(RC,k-neg[LC]-(val[x]<0));235 }236 }237 void insert(int p,int a){238 239 rotateTo(p-1,0);240 rotateTo(p,root);241 num[1]=a;242 makeTree(KT,1,1,ch[root][1]);243 pushup(ch[root][1]);244 pushup(root);245 }246 247 void insert(int p){248 int a=Q.top();Q.pop();249 insert(p+1,a);250 rotateTo(p+1,0);251 int posnum=sz[ch[root][0]]-neg[ch[root][0]]-1;252 if(posnum==neg[root]){253 insert(sz[root]-1,-a);254 }else{255 int k=find(root,posnum);256 insert(k,-a);257 }258 }259 void remove(int v){260 int x=pos[idx(v)];261 dele(x);262 x=pos[idx(-v)];263 dele(x);264 265 Q.push(v);266 }267 LL query(int v){268 int x1 = pos[idx(v)];269 int x2 = pos[idx(-v)];270 splay(x1,0);271 splay(x2,root);272 return sum[KT];273 }274 void init(){275 top1=top2=root=0;276 newNode(root,0);277 newNode(ch[root][1],0);278 fa[ch[root][1]]=root;279 pushup(ch[root][1]);280 pushup(root);281 }282 void solve(int n){283 int a;284 char op[10];285 Q.init(n+1);286 //for(int i=1;i<=n+1;i++)Q.push(i);287 for(int i=1;i<=n;i++){288 //debug();289 scanf("%s%d",op,&a);290 if(op[0]=='i'){291 insert(a);292 }else if(op[0]=='r'){293 remove(a);294 }else{295 printf("%I64d\n",query(a));296 }297 }298 }299 int num[N];300 int val[N];301 LL sum[N];302 int pos[N*2];303 int neg[N];304 xds Q;305 //priority_queue 
             
              
               ,greater
               
                 > Q;306 }spt;307 308 int main(){309 int n;310 int cas=1;311 while(scanf("%d",&n)!=EOF){312 printf("Case #%d:\n",cas++);313 spt.init();314 spt.solve(n);315 }316 }