题解 P3835 【【模板】可持久化平衡树】

在学替罪羊树的时候发现网上大部分博客都有这么一句话: “缺点：可持久化困难。” ~~感觉可持久化替罪羊挺好写的啊……反正我不会$fhq\space Treap$……~~ 我们知道可持久化数据结构的套路就是修改的时候边走边新建节点挂成链，比如主席树、可持久化$Trie$，我们一般是这样进行的，修改的时候递归操作，对当前节点复制一份，把不用访问的儿子指向原来节点的儿子（这样就节约了空间），然后要访问的那个儿子就递归下去。 我们发现这个用在线段树上面非常合适，因为他的祖先与后代的关系是恒定不变的，而平衡树就不太一样了。一般的平衡树都过于灵活，变化比较复杂，这主要是因为大部分平衡树都得旋转~~然后就父子关系乱伦~~，我们的可持久化的核心在于几个父亲共用一个儿子，所以$Splay$什么的不可持久化…… 然后不旋转的平衡树在$OI$中主要有两种：$fhq\space Treap$~~（然而我并不会）~~和替罪羊树。我们考虑把替罪羊树按照上面那种方式可持久化。 但是我们发现了一个严重的问题，这个替罪羊树虽然并不用旋转，但他的核心在于暴力拍扁重构，这样做可能会给父亲换掉一个儿子，然后这种多父一子的持久化关系就乱了。 其实我们发现重构也是暴力重构的，我们知道替罪羊树的一系列操作在时间上是均摊$O(nlogn)$的，我们原来进行可持久化的思路是在一条链的修改操作（单纯的插入删除）上进行节点复制挂成新的一条链，这样因为替罪羊树的树高本来就因为暴力重构比较平衡可以看做是$O(logn)$级别的，每次插入一条长度为树高级别的链，所以新建的节点个数是$O(nlogn)$级别的。然后我们现在在暴力重构的时候也进行节点的复制，让重构不影响原来的版本，仅影响当前的版本，然后就相当于所有修改操作都要复制一次节点，所以空间复杂度与其时间复杂度相当仍然是$O(nlogn)$的，并不会爆炸。 这么着看上去非常暴力，不过我写的可持久化替罪羊树在时间和空间上实测比很多人的$fhq\space Treap$的常数要小……替罪羊树真是个好东西…… 上代码~ ```cpp #include<iostream> #include<cstdio> #include<cstring> #define alpha (double)0.7//alpha设为0.7比较好 #define inf 2147483647 using namespace std; namespace ywy { inline int get() { int n=0; char c; while((c=getchar())||23333) { if(c>='0'&&c<='9')break; if(c=='-')goto s; } n=c-'0'; while((c=getchar())||23333) { if(c>='0'&&c<='9')n=n*10+c-'0'; else return(n); } s: while((c=getchar())||23333) { if(c>='0'&&c<='9')n=n*10-c+'0'; else return(n); } } void print(int num) { if(num<0)putchar('-'),num=-num; if(num>=10)print(num/10); putchar(num%10+'0'); } int data[30000001],ch[30000001][2],cnt[30000001],size[30000001],gn=1; inline void up(int tree) { size[tree]=size[ch[tree][0]]+size[ch[tree][1]]+cnt[tree]; } int nd[500001],ptr=1; void dfs(int tree)//在重构前先把子树的点找出来 { if(!tree)return; dfs(ch[tree][0]); if(cnt[tree])nd[ptr]=tree,ptr++; dfs(ch[tree][1]); } int digui(int l,int r)//暴力重构成高度严格logn的子树，注意仍然要进行节点复制 { if(l>r)return(0); int mid=(l+r)>>1; int tree=nd[mid]; int me=gn; gn++; data[me]=data[tree]; cnt[me]=cnt[tree]; ch[me][0]=digui(l,mid-1); ch[me][1]=digui(mid+1,r); up(me); return(me); } int root[500001]; int insert(int old,int num)//插入 { int tree=gn; gn++; data[tree]=data[old]; cnt[tree]=cnt[old]; size[tree]=size[old]+1;//节点复制 if(!old||data[old]==num) { data[tree]=num; ch[tree][0]=ch[old][0]; ch[tree][1]=ch[old][1];//注意不需要递归的时候记得把两个儿子都指一下 cnt[tree]++; return(tree); } int op=num>data[tree]; ch[tree][op^1]=ch[old][op^1]; ch[tree][op]=insert(ch[old][op],num); if((double)max(size[ch[tree][0]],size[ch[tree][1]])>(double)size[tree]*alpha) { ptr=1; dfs(tree); return(digui(1,ptr-1)); } return(tree); } int del(int old,int num)//删除，也要进行节点复制 { int tree=gn; gn++; data[tree]=data[old]; size[tree]=size[old]-1; cnt[tree]=cnt[old]; if(num==data[tree]) { cnt[tree]--; ch[tree][0]=ch[old][0]; ch[tree][1]=ch[old][1]; return(tree); } int op=num>data[tree]; ch[tree][op^1]=ch[old][op^1]; ch[tree][op]=del(ch[old][op],num); return(tree)； } int rankof(int tree,int rk)//剩下的跟普通平衡树就一样了~ { if(rk<=size[ch[tree][0]])return(rankof(ch[tree][0],rk)); rk-=size[ch[tree][0]]; if(rk<=cnt[tree])return(data[tree]); rk-=cnt[tree]; return(rankof(ch[tree][1],rk)); } inline int getrank(int num,int tree) { int ans=1,cur=tree; while(cur&&data[cur]!=num) { if(num>data[cur])ans+=cnt[cur]+size[ch[cur][0]],cur=ch[cur][1]; else cur=ch[cur][0]; } ans+=size[ch[cur][0]]; return(ans); } inline int find(int tree,int num) { int cur=tree; while(cur&&data[cur]!=num)cur=ch[cur][num>data[cur]]; if(!cnt[cur])return(inf); return(cur); } void ywymain() { int n=get(); for(register int i=1; i<=n; i++) { int ver=get(),cmd=get(),x=get(); if(cmd==1) { root[i]=insert(root[ver],x); } if(cmd==2) { if(find(root[ver],x)==inf)root[i]=root[ver]; else root[i]=del(root[ver],x); } if(cmd==3) { root[i]=root[ver]; print(getrank(x,root[i])); putchar('\n'); } if(cmd==4) { root[i]=root[ver]; print(rankof(root[i],x)); putchar('\n'); } if(cmd==5) { root[i]=root[ver]; int cjr=getrank(x,root[i]); if(cjr==1)print(-inf); else print(rankof(root[i],cjr-1)); putchar('\n'); } if(cmd==6) { root[i]=root[ver]; int me=find(root[i],x),rk; if(me==inf)rk=getrank(x,root[i]); else rk=getrank(x,root[i])+cnt[me]; if(rk>size[root[i]])print(inf); else print(rankof(root[i],rk)); putchar('\n'); } } } } int main() { ywy::ywymain(); return(0); } ```