正题

评测记录:/recordnew/lists?uid=SSL_WYC_zombieeeeee&pid=P3369&status=&sort=0

题目大意

要求支持查询一个数字的排名，查询该排名的数字，插入数字，删除数字，求前驱后继。

解题思路

替罪羊树

codecodecode

#include<cstdio>#include<algorithm>#include<cctype>#define alpha 0.8#define N 100010using namespace std;inline int read(){int x(0),sign(0);char ch=getchar();while(!isdigit(ch)){if(ch=='-') sign=1;ch=getchar();}while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return sign?-x:x;}struct goat_Tree{int l[N],r[N],size[N],val[N],valid[N],total[N];int cur[N],memory[N];bool exist[N];int root,poi,pool,cnt;void ReMemory(){for(int i=N-10;i>=1;i--)memory[++pool]=i;}bool Isbad(int now){if((double)valid[now]*alpha<=(double)max(valid[l[now]],valid[r[now]]))return true;else return false;}void Beat(int now){if(!now) return;Beat(l[now]);if(exist[now]) cur[++poi]=now;else memory[++pool]=now;Beat(r[now]);}void New(int x){l[x]=r[x]=0;total[x]=valid[x]=1;}void Build(int ls,int rs,int &now){int mid=(ls+rs)>>1;now=cur[mid];if(ls==rs){New(now);return;}if(ls<mid) Build(ls,mid-1,l[now]);else l[now]=0;Build(mid+1,rs,r[now]);total[now]=total[l[now]]+total[r[now]]+1;valid[now]=valid[l[now]]+valid[r[now]]+1;}void ReBuild(int &now){poi=0;Beat(now);if(poi) Build(1,poi,now);else now=0;}int GetRankByVal(int k){int now=root;int ans=1;while(now){if(val[now]>=k) now=l[now];else{ans+=valid[l[now]]+exist[now];now=r[now];}}return ans;}int GetValByRank(int k){int now=root;while(now){if(exist[now]&&valid[l[now]]+1==k)return val[now];if(valid[l[now]]>=k) now=l[now];else{k-=valid[l[now]]+exist[now];now=r[now];}}}void Insert(int &now,int num){if(!now){now=memory[pool--];val[now]=num;New(now);exist[now]=1;return;}total[now]++;valid[now]++;if(val[now]>=num) Insert(l[now],num);else Insert(r[now],num);if(Isbad(now))ReBuild(now);}void Remove_z(int &now,int tar){if(exist[now]&&valid[l[now]]+1==tar){exist[now]=0;valid[now]--;return;}valid[now]--;if(valid[l[now]]+exist[now]>=tar)Remove_z(l[now],tar);else Remove_z(r[now],tar-valid[l[now]]-exist[now]);}void Remove(int tar){Remove_z(root,GetRankByVal(tar));if((double)total[root]*alpha>valid[root])ReBuild(root);}}a;int main(){int opt,x,m;a.ReMemory();scanf("%d",&m);while(m--){opt=read();x=read();if(opt==1) a.Insert(a.root,x);if(opt==2) a.Remove(x);if(opt==3) printf("%d\n",a.GetRankByVal(x));if(opt==4) printf("%d\n",a.GetValByRank(x));if(opt==5) printf("%d\n",a.GetValByRank(a.GetRankByVal(x)-1));if(opt==6) printf("%d\n",a.GetValByRank(a.GetRankByVal(x+1)));}}