题目链接
题目大意：平衡树基础操作
题解：sbt模板……
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int M=100005;#define son(x,y) c[c[x][y]][y]int n,top,x;int c[M][2],sz[M],k[M];inline void pushup(int x){sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;}inline void node(int &x,int v){x=++top,c[x][0]=c[x][1]=0,sz[x]=1,k[x]=v;}void rotate(int &x,int k){ int y=c[x][k^1]; c[x][k^1]=c[y][k]; c[y][k]=x;sz[y]=sz[x]; pushup(x);x=y;}void insert(int &x,int v){ if(!x) node(x,v); else { sz[x]++;bool m=v>=k[x];//这里把相同元素插入x的右子树 insert(c[x][m],v); if(sz[son(x,m)]>sz[c[x][m^1]]) rotate(x,m^1); }}int PRe(int &x,int y,int v)//返回前驱的编号 { if(!x) return y; if(v>k[x]) return pre(c[x][1],x,v); return pre(c[x][0],y,v); }int suc(int &x,int y,int v)//后继 { if(!x) return y; if(v<k[x]) return suc(c[x][0],x,v); return suc(c[x][1],y,v); }int rk(int &x,int v)//求权值为x的排名 { if(!x) return 1; if(v>k[x]) return sz[c[x][0]]+1+rk(c[x][1],v); return rk(c[x][0],v);}int select(int &x,int w){ int r=sz[c[x][0]]+1; if (w<r) return select(c[x][0],w); if (w>r) return select(c[x][1],w-r); return k[x];}void del(int &x,int v) { if(!x) return ; sz[x]--; if(v!=k[x]) del(c[x][v>k[x]],v); else { int l=c[x][0],r=c[x][1]; if(l&&!r) x=l; else if(r&&!l) x=r; else if(!l&&!r) x=0; else//左右子树都有 { int y=c[x][1]; while(c[y][0]) y=c[y][0];//找到大于x的最小点来替换x k[x]=k[y]; del(c[x][1],k[y]); } }}void init(){ int p,a;x=0,top=0; cin>>n; for(int i=1;i<=n;i++) { scanf("%d%d",&p,&a); if(p==1) insert(x,a); if(p==2) del(x,a); if(p==3) printf("%d/n",rk(x,a)); if(p==4) printf("%d/n",select(x,a)); if(p==5) printf("%d/n",k[pre(x,0,a)]); if(p==6) printf("%d/n",k[suc(x,0,a)]); }}int main(){ init(); return 0;}新闻热点
疑难解答
