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

这个题也是可以用可持久化线段树来解决的。 值域线段树（也有的叫权值线段树）可以用来维护一个可重集，并实现一些一般情况下平衡树才能实现的事情。 如果用值来当做区间左右端点，每个叶子节点上存某个值出现的次数，非叶子节点上存一定范围内的值出现的总次数，就可以建成值域线段树。可以在上面直接查询第k大值、小于某值的数的个数等等，具体请百度或参见代码。 如何将线段树可持久化呢？线段树在单点更新的时候会经过log n个节点，每一次更新时显然也只有这么多节点会发生变化。 记录每一个版本的线段树的根节点，每一次操作前将根节点赋为与这次操作基于的版本的根节点相同。在更新操作时，备份每一个经过的节点（包括各个属性：左、右子树以及区间和），然后再进行修改。具体也可以参考[可持久化线段树](https://www.luogu.org/problemnew/show/P3919)的题解。 如果直接用可持久化的值域线段树，显然空间是不够的（4\*2e9个节点啊...）。现在有两种选择： 1.发现这道题没有加、减操作，所有操作涉及的值都是确定的。因此可以进行离散化，然后再做，想必可以A掉吧~~（我没试过）~~ 2.可以写动态开点线段树。题目要求的集合一开始是空的，因此如果一开始建一棵完整的线段树的话，每一个节点记录的区间和都是0。而总共只有5e5次操作，每一次操作涉及更改节点最多有log2(2e9)=31个，两者乘起来远远小于4\*2e9。 可以考虑一开始不真正建树。规定：如果某节点的某个子节点是一个特殊的标记的话，表明以这个子节点为根的子树还没有实际建出来。显然，一个子树没有实际建出来的时候，其表示的区间的和为0。（以下代码中我用的标记是0） 在进行修改操作的时候，可能需要建出来要走入的那个子节点。在进行查询操作的时候，可以把未建出的子节点的区间和当做0。 附：写完后我发现前驱和后继竟然是最难写的... 附：注意各种对不存在的节点的查询/要忽略的操作 附：注意代码中有一些操作用到的变量被设置成了全局变量，还define了一个mid，表示区间中点，可能比较奇怪... [博客](http://www.cnblogs.com/hehe54321/p/8530074.html) ``` #include<cstdio> #include<algorithm> #include<cstring> #include<bits/stdc++.h> #define mid ((l+r)>>1) #define inf 2147483647 using namespace std; int lc[20000000],rc[20000000],root[20000000],dat[20000000],ll=-1e9,rr=1e9; //lc[i]、rc[i]分别表示节点i的左子节点、右子节点编号，如果lc[x]=0则表示x的左子树尚未建出来，rc[x]同理 //dat[i]表示节点i表示的值域区间中各数的出现次数之和 int n,L,x,mem=1;//因为0号被"未实际建出的节点"的特殊标记占用了，1号被版本0的根节点占用了 void addx(int l,int r,int& num)//更新操作，将线段树维护的集合中数L的出现次数加上x（x为1或-1） { int t=num;num=++mem;lc[num]=lc[t];rc[num]=rc[t];dat[num]=dat[t];//备份当前节点，如果当前节点原来为空则也可以完成 if(l==r) { if(!(dat[num]==0&&x<0)) dat[num]+=x;//如果L出现次数为0且操作为删除操作，则忽略操作 return; } if(L<=mid) addx(l,mid,lc[num]); else addx(mid+1,r,rc[num]); dat[num]=0; if(lc[num]) dat[num]+=dat[lc[num]]; if(rc[num]) dat[num]+=dat[rc[num]];//维护当前节点信息 } int query(int l,int r,int num)//查询集合中小于x的数的个数 { if(l==r) return 0;//如果已经到叶子节点了，那么当前节点等于x，显然不小于x if(!num) return 0;//如果当前节点为空，那么该节点表示的子树中数都没有，自然返回0 if(x<=mid) return query(l,mid,lc[num]);//根据x决定向左/右子树走 else return (lc[num]?dat[lc[num]]:0)+query(mid+1,r,rc[num]); } int query_kth(int l,int r,int k,int num)//查询第k小数 { assert(num!=0);//assert(x)表示如果x为false则停止程序，是用来调试的。如果查询操作是正常进行的，那么不可能走到未建出的点中 if(l==r) {return l;} //if(!num) return 0;//没有用 int ls=lc[num]?dat[lc[num]]:0; if(ls>=k) return query_kth(l,mid,k,lc[num]);//根据左子树中数出现总次数决定向左/右子树走 else return query_kth(mid+1,r,k-ls,rc[num]); } int query_time(int l,int r,int num)//查询数x出现的次数 { while(l!=r) { if(!num) return 0;//当前节点未建出，表明其子节点均未出现 if(L<=mid) r=mid,num=lc[num]; else l=mid+1,num=rc[num]; } return dat[num]; } int query_pre(int l,int r,int num)//查询数x的前驱 { int t=query(l,r,num);//t是集合中比x小的数的个数 if(t==0) return -inf;//如果集合中比x小的数有0个，则x是集合中最小的数，不存在前驱 return query_kth(l,r,t,num);//否则查询集合中第t小即可 } int query_nxt(int l,int r,int num) { int t1=query(l,r,num),t2=query_time(l,r,num);//t1是集合中比x小的数的个数,t2是集合中x出现的次数，加起来是集合中小于等于x的数的个数 x=inf;int t3=query(l,r,num); if(t1+t2==t3) return inf;//如果集合中小于等于x的数与集合中小于等于inf的数相等，则x是集合中最大的数，不存在后继 return query_kth(l,r,t1+t2+1,num);//否则查询集合中第t1+t2+1小即可 } int main() { int i,v,idx; scanf("%d",&n); root[0]=1; for(i=1;i<=n;i++) { scanf("%d%d%d",&v,&idx,&x);root[i]=root[v]; if(idx==1) { L=x;x=1; addx(ll,rr,root[i]); } else if(idx==2) { L=x;x=-1; addx(ll,rr,root[i]); } else if(idx==3) { printf("%d\n",query(ll,rr,root[i])+1); } else if(idx==4) { printf("%d\n",query_kth(ll,rr,x,root[i])); } else if(idx==5) { L=x; printf("%d\n",query_pre(ll,rr,root[i])); } else if(idx==6) { L=x; printf("%d\n",query_nxt(ll,rr,root[i])); } } return 0; } ```