正題

題目鏈接:https://www.luogu.com.cn/problem/P3835

---

題目大意

一個空可重集，要求支持

• 插入一個數$x$
• 刪除一個數$x$
• 詢問一個數$x$的排名
• 詢問排名第$x$的數字
• 詢問$x$的前驅
• 詢問$x$的后繼

但是所有操作都是基于某個歷史版本

$1\le n\le 5\times 10^5,1\le |x|\le 10^9$

---

解題思路

挺好寫的，就是一個$FHQ$，可持久化部分分裂和主席樹差不多，合并和線段樹合并差不多。
空間記得開大點。

時空間復雜度都是$O(n\log n)$的。

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e7+10; int n,rt[510000]; struct FHQ{int cnt,w[N],siz[N],rnk[N],t[N][2];int NewNode(int val){w[++cnt]=val;siz[cnt]=1;rnk[cnt]=rand();return cnt;}void PushUp(int x){siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;}void Cpy(int x,int y){siz[x]=siz[y];rnk[x]=rnk[y];w[x]=w[y];t[x][0]=t[y][0];t[x][1]=t[y][1];return;}void Split(int &x,int &y,int p,int k){if(!p){x=y=0;return;}int now=++cnt;Cpy(now,p);if(w[p]<=k)x=now,Split(t[now][1],y,t[p][1],k);else y=now,Split(x,t[now][0],t[p][0],k);PushUp(now);return;}int Merge(int x,int y){if(!x||!y)return x|y;int now=++cnt;if(rnk[x]<=rnk[y]){Cpy(now,x);t[now][1]=Merge(t[x][1],y);}else{Cpy(now,y);t[now][0]=Merge(x,t[y][0]);}PushUp(now);return now;}int Find(int x,int k){if(siz[t[x][0]]>=k)return Find(t[x][0],k);if(siz[t[x][0]]+1==k)return x;return Find(t[x][1],k-siz[t[x][0]]-1);}void Insert(int &rt,int val){int x,y;Split(x,y,rt,val);rt=Merge(Merge(x,NewNode(val)),y);return;}void Delete(int &rt,int val){int x,y,z;Split(x,z,rt,val);Split(x,y,x,val-1);y=Merge(t[y][0],t[y][1]);rt=Merge(Merge(x,y),z);return;}int GetRank(int rt,int val){int x,y;Split(x,y,rt,val-1);return siz[x]+1;}int GetVal(int rt,int rk){return w[Find(rt,rk)];}int GetPre(int rt,int val){int x,y;Split(x,y,rt,val-1);return w[Find(x,siz[x])];}int GetNxt(int rt,int val){int x,y;Split(x,y,rt,val);return w[Find(y,1)];} }T; int main() {scanf("%d",&n);T.NewNode(-2147483647);T.NewNode(2147483647);rt[0]=T.Merge(1,2);for(int i=1,v,op,x;i<=n;i++){scanf("%d%d%d",&v,&op,&x);rt[i]=rt[v];if(op==1)T.Insert(rt[i],x);else if(op==2)T.Delete(rt[i],x);else if(op==3)printf("%d\n",T.GetRank(rt[i],x)-1);else if(op==4)printf("%d\n",T.GetVal(rt[i],x+1));else if(op==5)printf("%d\n",T.GetPre(rt[i],x));else if(op==6)printf("%d\n",T.GetNxt(rt[i],x));}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P3835-[模板]可持久化平衡树【无旋Treap】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。