解题：洛谷3835 可持久化平衡树

题面
其实就是在Merge和Split的时候换成新建节点，然后把原来的节点整个拷到新的节点一份继续做
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  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
",rnk_query(root[i],t3));
110         else if(t2==4) printf("%d
",num_query(root[i],t3));
111         else if(t2==5) printf("%d
",pre_query(root[i],t3));
112         else if(t2==6) printf("%d
",nxt_query(root[i],t3));
113     }
114     return 0;
115 }
View Code