题面
其实就是在Merge和Split的时候换成新建节点，然后把原来的节点整个拷到新的节点一份继续做
1 #include2 #include 3 #include 4 using namespace std; 5 const int N=500005,inf=2147483647; 6 int root[N],siz[N*50],son[N*50][2],rnk[N*50],val[N*50]; 7 int n,x,y,z,t1,t2,t3,tot; 8 void Copy(int a,int b) 9 { 10 son[a][0]=son[b][0]; 11 son[a][1]=son[b][1]; 12 siz[a]=siz[b],rnk[a]=rnk[b],val[a]=val[b]; 13 } 14 void Pushup(int nde) 15 { 16 siz[nde]=siz[son[nde][0]]+siz[son[nde][1]]+1; 17 } 18 int Create(int tsk) 19 { 20 siz[++tot]=1; 21 val[tot]=tsk; 22 rnk[tot]=rand(); 23 return tot; 24 } 25 int Merge(int x,int y) 26 { 27 if(!x||!y) return x+y; 28 else if(rnk[x]<=rnk[y]) 29 { 30 int newn=++tot; Copy(newn,x); 31 son[newn][1]=Merge(son[newn][1],y); 32 Pushup(newn); return newn; 33 } 34 else 35 { 36 int newn=++tot; Copy(newn,y); 37 son[newn][0]=Merge(x,son[newn][0]); 38 Pushup(newn); return newn; 39 } 40 } 41 void Split(int nde,int &x,int &y,int tsk) 42 { 43 if(!nde) x=y=0; 44 else 45 { 46 if(val[nde]<=tsk) 47 { 48 x=++tot,Copy(x,nde); 49 Split(son[x][1],son[x][1],y,tsk); 50 Pushup(x); 51 } 52 else 53 { 54 y=++tot,Copy(y,nde); 55 Split(son[y][0],x,son[y][0],tsk); 56 Pushup(y); 57 } 58 } 59 } 60 int Query(int nde,int tsk) 61 { 62 if(tsk<=siz[son[nde][0]]) return Query(son[nde][0],tsk); 63 else if(tsk==siz[son[nde][0]]+1) return nde; 64 else return Query(son[nde][1],tsk-siz[son[nde][0]]-1); 65 } 66 void Insert(int &trt,int tsk) 67 { 68 Split(trt,x,y,tsk); 69 trt=Merge(Merge(x,Create(tsk)),y); 70 } 71 void Delete(int &trt,int tsk) 72 { 73 Split(trt,x,z,tsk),Split(x,x,y,tsk-1); 74 trt=Merge(Merge(x,Merge(son[y][0],son[y][1])),z); 75 } 76 int rnk_query(int &trt,int tsk) 77 { 78 Split(trt,x,y,tsk-1); 79 int ret=siz[x]+1; 80 trt=Merge(x,y); return ret; 81 } 82 int num_query(int &trt,int tsk) 83 { 84 return val[Query(trt,tsk)]; 85 } 86 int pre_query(int &trt,int tsk) 87 { 88 Split(trt,x,y,tsk-1); 89 int ret=val[Query(x,siz[x])]; 90 trt=Merge(x,y); 91 return x?ret:-inf; 92 } 93 int nxt_query(int &trt,int tsk) 94 { 95 Split(trt,x,y,tsk); 96 int ret=val[Query(y,1)]; 97 trt=Merge(x,y); 98 return y?ret:inf; 99 }100 int main()101 {102 srand(20020513);103 scanf("%d",&n);104 for(int i=1;i<=n;i++)105 {106 scanf("%d%d%d",&t1,&t2,&t3),root[i]=root[t1];107 if(t2==1) Insert(root[i],t3);108 else if(t2==2) Delete(root[i],t3);109 else if(t2==3) printf("%d\n",rnk_query(root[i],t3));110 else if(t2==4) printf("%d\n",num_query(root[i],t3));111 else if(t2==5) printf("%d\n",pre_query(root[i],t3));112 else if(t2==6) printf("%d\n",nxt_query(root[i],t3));113 }114 return 0;115 }