http://www.lydsy.com/JudgeOnline/problem.php?id=3224?(題目鏈接)

題意

　　1. 插入x數；2. 刪除x數(若有多個相同的數，因只刪除一個)；3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)；4. 查詢排名為x的數；5. 求x的前驅(前驅定義為小于x，且最大的數)；6. 求x的后繼(后繼定義為大于x，且最小的數)

Solution

　　treap板子。右轉光勛總結→_→：平衡樹

細節

　　一個節點還統計了這個數出現了幾次，然后詢問排名前驅后繼什么的寫的我蛋都要碎了T_T，所以這里旋轉版的rank求的是小于$x$的數的個數，而不是$x$的排名。

旋轉treap

// bzoj3224 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 2147483640 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std;const int maxn=100010; int n,sz,Dargen; struct node {int son[2],size,val,rnd,w;int& operator [] (int x) {return son[x];} }tr[maxn];void pushup(int k) {tr[k].size=tr[tr[k][0]].size+tr[tr[k][1]].size+tr[k].w; } void rotate(int &x,int p) { //記得&int y=tr[x][p];tr[x][p]=tr[y][p^1];tr[y][p^1]=x;x=y; //記得寫x=ypushup(tr[y][p^1]);pushup(y); } void insert(int &k,int x) {if (!k) {tr[k=++sz].val=x;tr[k].rnd=rand();tr[k].size=tr[k].w=1;return;}int p=x>tr[k].val;tr[k].size++;if (tr[k].val==x) {tr[k].w++;return;}insert(tr[k][p],x);if (tr[tr[k][p]].rnd>tr[k].rnd) rotate(k,p); } void erase(int &k,int x) {if (k==0) return;if (tr[k].val==x) {if (tr[k].w>1) {tr[k].w--;tr[k].size--;return;}if (tr[k][0]*tr[k][1]==0) k=tr[k][0]+tr[k][1];else rotate(k,tr[tr[k][0]].rnd<tr[tr[k][1]].rnd),erase(k,x);}else tr[k].size--,erase(tr[k][x>tr[k].val],x); } int find(int k,int x) {if (!k) return 0;if (tr[tr[k][0]].size<x && x<=tr[tr[k][0]].size+tr[k].w) return tr[k].val;else if (x<=tr[tr[k][0]].size) return find(tr[k][0],x);else return find(tr[k][1],x-tr[tr[k][0]].size-tr[k].w); } int rank(int k,int x) {if (!k) return 0;if (x<=tr[k].val) return rank(tr[k][0],x);else return rank(tr[k][1],x)+tr[tr[k][0]].size+tr[k].w; } int main() {scanf("%d",&n);for (int op,x,i=1;i<=n;i++) {scanf("%d%d",&op,&x);if (op==1) insert(Dargen,x);if (op==2) erase(Dargen,x);if (op==3) printf("%d\n",rank(Dargen,x)+1);if (op==4) printf("%d\n",find(Dargen,x));if (op==5) printf("%d\n",find(Dargen,rank(Dargen,x)));if (op==6) printf("%d\n",find(Dargen,rank(Dargen,x+1)+1));}return 0; }

非旋轉treap

// bzoj3224 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 2147483640 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std;const int maxn=100010; int n,sz,Dargen; struct node {int son[2],size,val,rnd;int& operator [] (int x) {return son[x];} }tr[maxn];void pushup(int k) {tr[k].size=tr[tr[k][0]].size+tr[tr[k][1]].size+1; } void split(int k,int x,int &a,int &b) {if (!x) {a=0;b=k;return;}int l=tr[k][0],r=tr[k][1];if (tr[l].size==x) tr[k][0]=0,a=l,b=k;else if (tr[l].size+1==x) tr[k][1]=0,a=k,b=r;else if (x<tr[l].size) split(l,x,a,tr[k][0]),b=k;else split(r,x-tr[l].size-1,tr[k][1],b),a=k;pushup(k); } int merge(int x,int y) { //按順序x<yif (!x || !y) return x|y;if (tr[x].rnd>tr[y].rnd) {tr[x][1]=merge(tr[x][1],y);pushup(x);return x;}else {tr[y][0]=merge(x,tr[y][0]);pushup(y);return y;} } int rank(int k,int x) {if (!k) return 1;if (x<=tr[k].val) return rank(tr[k][0],x);else return rank(tr[k][1],x)+tr[tr[k][0]].size+1; } int find(int k,int x) {if (!k) return 0;if (tr[tr[k][0]].size+1==x) return tr[k].val;else if (x<=tr[tr[k][0]].size) return find(tr[k][0],x);else return find(tr[k][1],x-tr[tr[k][0]].size-1); } void insert(int x) {int l,r;tr[++sz].val=x;tr[sz].rnd=rand();tr[sz].size=1;split(Dargen,rank(Dargen,x)-1,l,r);Dargen=merge(merge(l,sz),r); } void erase(int k) {int x,y;split(Dargen,k,x,y);split(x,k-1,x,k);Dargen=merge(x,y); } int main() {scanf("%d",&n);for (int op,x,i=1;i<=n;i++) {scanf("%d%d",&op,&x);if (op==1) insert(x);if (op==2) erase(rank(Dargen,x));if (op==3) printf("%d\n",rank(Dargen,x));if (op==4) printf("%d\n",find(Dargen,x));if (op==5) printf("%d\n",find(Dargen,rank(Dargen,x)-1));if (op==6) printf("%d\n",find(Dargen,rank(Dargen,x+1)));}return 0; }

?

轉載于:https://www.cnblogs.com/MashiroSky/p/6486539.html

總結

以上是生活随笔為你收集整理的【bzoj3224】 Tyvj1728—普通平衡树的全部內容，希望文章能夠幫你解決所遇到的問題。

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