首页 > 代码库 > hdu 3436
hdu 3436
一开始，直接无脑的对n数组维护。打完之后一看n的范围，默默的删了。
一看范围，就知道要先读进来询问，把涉及到的x做一个统计，这样n的数组
1,2,...,n
(1,x0-1),x0,(x0+1,x1),x1,...,n
这样子就缩好了（一个节点是一个区间）。记录每个节点的起始数。
统计的信息，区间和（即数的个数）。
这样三个操作都能写啦。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <map> 6 #include <set> 7 8 #define KT ch[ch[root][1]][0] 9 #define LC ch[x][0] 10 #define RC ch[x][1] 11 #define N 310001 12 using namespace std; 13 14 struct node{ 15 char op[10]; 16 int x; 17 void in(){ 18 scanf("%s%d",op,&x); 19 } 20 }; 21 struct SplayTree{ 22 int root; 23 int fa[N]; 24 int ch[N][2]; 25 int sz[N]; 26 int top1; 27 int top2; 28 int ss[N]; 29 int que[N]; 30 31 void pushdown(int x){ 32 33 } 34 void pushup(int x){ 35 sz[x]=1+sz[LC]+sz[RC]; 36 sum[x]=val[x]+sum[LC]+sum[RC]; 37 } 38 void rotate(int x,bool f){ 39 int y=fa[x]; 40 int z=fa[y]; 41 pushdown(y); 42 pushdown(x); 43 ch[y][!f]=ch[x][f]; 44 fa[ch[x][f]]=y; 45 fa[x]=z; 46 if (z) { 47 ch[z][ch[z][1]==y] = x; 48 } 49 ch[x][f] = y; 50 fa[y]=x; 51 pushup(y); 52 } 53 void splay(int x, int g) { 54 int y = fa[x]; 55 pushdown(x); 56 while(y!=g){ 57 int z= fa[y]; 58 bool f = (ch[y][0]==x); 59 if(z != g && f == (ch[z][0]==y)){ 60 rotate(y,f); 61 } 62 rotate(x,f); 63 y=fa[x]; 64 } 65 pushup(x); 66 if(g==0) root = x; 67 } 68 void rotateTo(int k,int g) { 69 int x=root; 70 pushdown(x); 71 while(sz[LC] != k){ 72 if(k<sz[LC]){ 73 x=LC; 74 }else{ 75 k -= sz[LC] + 1; 76 x = RC; 77 } 78 pushdown(x); 79 } 80 splay(x,g); 81 } 82 void build(int l,int r,int f){ 83 if(l>r){ 84 return ; 85 } 86 int x = (l + r) >> 1; 87 LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0; 88 RC = (r >= x + 1)? (x + 1 + r)>> 1 :0; 89 fa[x] = f; 90 build(l,x - 1,x); 91 build(x + 1,r,x); 92 pushup(x); 93 } 94 void erase(int x){ 95 if(x==0) 96 return; 97 int father= fa[x]; 98 int head = 0, tail=0; 99 for(que[tail++] =x ; head < tail; head++){100 ss[top2++] = que[head];101 if(ch[que[head]][0]){102 que[tail++]=ch[que[head]][0];103 }104 if(ch[que[head]][1]){105 que[tail++] = ch[que[head]][1];106 }107 }108 ch[father][ch[father][1]==x]=0;109 pushup(father);110 }111 void treaval(int x){112 if (x) {113 pushdown(x);114 treaval(LC);115 printf("@%d",val[x]);116 //ans[cnt++]=val[x];117 treaval(RC);118 }119 }120 void newNode(int &x,int c,int r,int st){121 if(top2){122 x = ss[--top2];123 } else {124 x = ++top1;125 }126 LC = RC = fa[x] =0;127 sz[x] = 1;128 val[x] = c;129 ret[x] = r;130 start[x]=st;131 132 if(r&&pos.find(r)==pos.end()){133 pos[r]=x;134 }135 136 }137 void makeTree(int &x, int l, int r, int f){138 if(l > r){139 return;140 }141 int m=(l+r)>>1;142 143 newNode(x, num[m], m%2?a[m/2]:0,b[m]);144 makeTree(LC,l,m-1,x);145 makeTree(RC,m+1,r,x);146 fa[x]=f;147 pushup(x);148 }149 void debug(){150 treaval(root);151 cout<<endl;152 }153 void cutTo(int l,int r,int c){154 rotateTo(l-1,0);155 rotateTo(r+1,root);156 //debug();157 int tmp=KT;158 KT=0;159 pushup(ch[root][1]);160 pushup(root);161 rotateTo(c,0);162 rotateTo(c+1,root);163 fa[tmp]=ch[root][1];164 KT=tmp;165 pushup(ch[root][1]);166 pushup(root);167 //debug();168 }169 int find(int x,int k){170 if(sum[LC]<=k-1&&sum[LC]+val[x]>=k){171 return start[x]+k-sum[LC]-1;172 }173 else if(sum[LC]>=k){174 return find(LC,k);175 }else {176 return find(RC,k-sum[LC]-val[x]);177 }178 }179 void init(int n,int m){180 pos.clear();181 top1=top2=root=0;182 newNode(root,0,0,0);183 newNode(ch[root][1],0,0,0);184 fa[ch[root][1]]=root;185 for(int i=0;i<m;i++)186 {187 Q[i].in();188 aa[i]=Q[i].x;189 }190 sort(aa,aa+m);191 a[0]=aa[0];192 int cnt=1;193 for(int i=1;i<m;i++){194 if(aa[i]!=aa[i-1])195 a[cnt++]=aa[i];196 }197 m=cnt;198 num[0]=a[0]-1;199 b[0]=1;200 for(int i=0;i<m;i++){201 if(i!=0){202 num[i*2]=a[i]-a[i-1]-1;203 b[i*2]=a[i-1]+1;204 }205 num[i*2+1]=1;206 b[i*2+1]=a[i];207 }208 num[m*2]=n-a[m-1];209 b[m*2]=a[m-1]+1;210 makeTree(KT,0,2*m,ch[root][1]);211 pushup(ch[root][1]);212 pushup(root);213 }214 void top(int v){215 int x=pos[v];216 splay(x,0);217 int k=sz[ch[root][0]];218 219 cutTo(k,k,0);220 }221 int rank(int k){222 223 return find(root,k);224 }225 int query(int v){226 int x=pos[v];227 splay(x,0);228 //debug();229 return sum[LC]+1;230 }231 void solve(int m){232 233 int v;234 for(int i=0;i<m;i++){235 // debug();236 v=Q[i].x;237 if(Q[i].op[0]==‘T‘){238 top(v);239 }else if(Q[i].op[0]==‘R‘){240 printf("%d\n",rank(v));241 }else{242 printf("%d\n",query(v));243 }244 }245 }246 int val[N];//数值247 int sum[N];248 int ret[N];//结果249 int start[N];//该区间开始的数；250 251 int aa[N];252 int a[N];253 int b[N];254 int num[N];255 //int pos[N];256 map<int,int>pos;257 node Q[N];258 }spt;259 260 int main()261 {262 int T;263 cin>>T;264 int n,m;265 int cas=1;266 while(T--){267 scanf("%d%d",&n,&m);268 printf("Case %d:\n",cas++);269 spt.init(n,m);270 spt.solve(m);271 }272 return 0;273 }
hdu 3436
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。