可持久化普通平衡樹

題意

如題。

解法

大家都知道，用權(quán)值線段樹可以過普通平衡樹那道題，那么對于可持久化普通平衡樹，我們是否也可以用主席樹來搞一搞呢。答案是肯定的。只需要動態(tài)開點就行了。其他的跟普通平衡樹那道題一模一樣。

代碼

這里需要注意一點，當 l 和 r 都是負數(shù)的時候， /2 就會有問題，因為 $ -5/2 = -2$ 而 $ -5 >> 1 = -3$ ，所以除2會使 l 一直小于mid，從而陷入死循環(huán)。

#include <bits/stdc++.h> #define INF 2147483647 using namespace std; template <typename T> inline void read(T &x) {x=0;T k=1;char c=getchar();while(!isdigit(c)) {if(c=='-') k=-1;c=getchar();}while(isdigit(c)) {x=x*10+c-'0';c=getchar();}x*=k; }const int maxn=5e5+5; const int ll=-1e9,rr=1e9; struct node {int lc,rc,sum; }T[maxn*40];int root[maxn],sz;void update(int l,int r,int pos,int val,int &x,int y) {T[++sz]=T[y],x=sz;if(l==r) {if(!(T[x].sum==0&&val<0)) T[x].sum+=val;return;}int mid=(l+r)>>1;if(pos<=mid) update(l,mid,pos,val,T[x].lc,T[y].lc);else update(mid+1,r,pos,val,T[x].rc,T[y].rc);T[x].sum=T[T[x].lc].sum+T[T[x].rc].sum; }int query(int l,int r,int pos,int x) {if(l==r) return 0;int mid=(l+r)>>1;if(pos<=mid) return query(l,mid,pos,T[x].lc);return T[T[x].lc].sum+query(mid+1,r,pos,T[x].rc); }int kth(int l,int r,int k,int x) {if(l==r) return l;int mid=(l+r)>>1,sum=T[T[x].lc].sum;if(k<=sum) return kth(l,mid,k,T[x].lc);else return kth(mid+1,r,k-sum,T[x].rc); }int pre(int l,int r,int pos,int x) {int k=query(l,r,pos,x);if(k==0) return -INF;else return kth(l,r,k,x); }int query_muilt(int l,int r,int pos,int x) {if(l==r) return T[x].sum;int mid=(l+r)>>1;if(pos<=mid) return query_muilt(l,mid,pos,T[x].lc);else return query_muilt(mid+1,r,pos,T[x].rc); }int nxt(int l,int r,int pos,int x) {int a1=query(l,r,pos,x),a2=query_muilt(l,r,pos,x);if(a1+a2==T[x].sum) return INF;return kth(l,r,a1+a2+1,x); }int n; int main() {read(n);for(int i=1;i<=n;i++) {int v,opt,x;read(v),read(opt),read(x);switch(opt) {case 1 : {update(ll,rr,x,1,root[i],root[v]);break;} case 2 : {update(ll,rr,x,-1,root[i],root[v]);break;} case 3 : {root[i]=root[v],printf("%d\n",query(ll,rr,x,root[i])+1);break;} case 4 : {root[i]=root[v],printf("%d\n",kth(ll,rr,x,root[i]));break;} case 5 : {root[i]=root[v],printf("%d\n",pre(ll,rr,x,root[i]));break;} case 6 : {root[i]=root[v],printf("%d\n",nxt(ll,rr,x,root[i]));break;} }}return 0; } /* 10 0 1 9 1 1 3 1 1 10 2 4 2 3 3 9 3 1 2 6 4 1 6 2 9 8 6 3 4 5 8*/

轉(zhuǎn)載于:https://www.cnblogs.com/mrasd/p/9532263.html

總結(jié)

以上是生活随笔為你收集整理的可持久化平衡树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。