本文主要是介绍P3369 【模板】普通平衡树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
[题目通道](【模板】普通平衡树 - 洛谷）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7;
#define int long longstruct node
{int l;int r;int val;int sval;int size;
};
node tree[maxn];
int root=0;
int idx=0;void newnode(int &x,int v)
{x=++idx;tree[idx].val=v;tree[idx].sval=rand();tree[idx].size=1;
}void pushup(int pos)
{tree[pos].size=tree[tree[pos].l].size+tree[tree[pos].r].size+1;
}void split(int pos,int val,int &x,int &y)//按值分裂,取决于树的路径长，O(log n)
{if(!pos){x=y=0;return;}if(tree[pos].val<=val){x=pos;split(tree[x].r,val,tree[x].r,y);pushup(x);}else{y=pos;split(tree[y].l,val,x,tree[y].l);pushup(y);}
}int merge(int x,int y)//只需要考虑两棵树根节点的大小，因为它们内部都是有序的。返回值为新树的根节点，O(log n)
{if(!x||!y)return x+y;if(tree[x].sval<tree[y].sval){tree[x].r=merge(tree[x].r,y);pushup(x);return x;}else{tree[y].l=merge(x,tree[y].l);pushup(y);return y;}
}void ins(int v)
{int x,y,z;split(root,v,x,y);newnode(z,v);root=merge(merge(x,z),y);
}void del(int v)
{ int x,y,z; split(root,v,x,z);split(x,v-1,x,y);y=merge(tree[y].l,tree[y].r);root=merge(merge(x,y),z);
}int kth(int pos,int k)
{if(k==tree[tree[pos].l].size+1){return tree[pos].val;}else if(k<=tree[tree[pos].l].size){return kth(tree[pos].l,k);}else{return kth(tree[pos].r,k-tree[tree[pos].l].size-1);}
}int pre(int val)
{int x,y;split(root,val-1,x,y);int ans=kth(x,tree[x].size);root=merge(x,y);return ans;
}int suc(int val)
{int x,y;split(root,val,x,y);int ans=kth(y,1);root=merge(x,y);return ans;
}int getrank(int val)
{int x,y;split(root,val-1,x,y);int ans=tree[x].size+1;root=merge(x,y);return ans;
}signed main()
{int n=0,op=0,s=0;cin>>n;for(int i=1;i<=n;i++){cin>>op>>s;if(op==1){ins(s);}if(op==2){del(s);}if(op==3){cout<<getrank(s);if(i<n)cout<<endl;}if(op==4){cout<<kth(root,s);if(i<n)cout<<endl;}if(op==5){cout<<pre(s);if(i<n)cout<<endl;}if(op==6){cout<<suc(s);if(i<n)cout<<endl;}}return 0;
}这篇关于P3369 【模板】普通平衡树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
