【Luogu3369】普通平衡树

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+4; int n,rt,pool=0; struct node{ int lc,rc,fa,size,key,pri,cnt; }a[maxn]; inline void zig(int &k){ int y=a[k].lc; a[k].lc=a[y].rc; a[y].rc=k; a[y].size=a[a[y].lc].size+a[a[y].rc].size+a[y].cnt; a[k].size=a[a[k].lc].size+a[a[k].rc].size+a[k].cnt; k=y; } inline void zag(int &k){ int y=a[k].rc; a[k].rc=a[y].lc; a[y].lc=k; a[y].size=a[a[y].lc].size+a[a[y].rc].size+a[y].cnt; a[k].size=a[a[k].lc].size+a[a[k].rc].size+a[k].cnt; k=y; } inline void insert(int &k,int key){ if(!k){ k=++pool; a[k].key=key;a[k].pri=rand(); a[k].cnt=a[k].size=1; a[k].lc=a[k].rc=0; return; } if(a[k].key==key) ++a[k].cnt; else if(key<a[k].key){ insert(a[k].lc,key); if(a[a[k].lc].pri<a[k].pri) zig(k); }else{ insert(a[k].rc,key); if(a[a[k].rc].pri<a[k].pri) zag(k); } a[k].size=a[a[k].lc].size+a[a[k].rc].size+a[k].cnt; return; } inline void delete1(int &k,const int &key){ if(!k) return; if(a[k].key==key){ if(a[k].cnt>1) a[k].cnt--; else if (!a[k].lc||!a[k].rc) k=a[k].lc+a[k].rc; else if(a[a[k].lc].pri<a[a[k].rc].pri) zig(k),delete1(k,key); else zag(k),delete1(k,key); } else if(key<a[k].key) delete1(a[k].lc,key); else delete1(a[k].rc,key); a[k].size=a[a[k].lc].size+a[a[k].rc].size+a[k].cnt; return; } inline int queryRank(const int &key){ int x=rt,res=0,lc,rc; while(x){ lc=a[x].lc,rc=a[x].rc; if(a[x].key==key) return res+a[lc].size+1; if(key<a[x].key) x=lc; else res+=a[lc].size+a[x].cnt,x=rc; } return res; } inline int queryKey(int k){ int x=rt,lc,rc; while(x){ lc=a[x].lc,rc=a[x].rc; if(a[lc].size<k&&a[lc].size+a[x].cnt>=k) return a[x].key; else if(a[lc].size>=k) x=lc; else k-=a[lc].size+a[x].cnt,x=rc; } return 0; } inline int queryQian(int key){ int x=rt,res=-0x3f3f3f3f; while(x){ if(a[x].key<key) { res=a[x].key; x=a[x].rc; }else x=a[x].lc; } return res; } inline int queryHou(int key){ int x=rt,res=0x3f3f3f3f; while(x){ if(a[x].key>key) { res=a[x].key; x=a[x].lc; }else x=a[x].rc; } return res; } int main(){ cin>>n; for(int i=1;i<=n;i++){ int opt,x;scanf("%d%d",&opt,&x); if(opt==1){ insert(rt,x); }else if(opt==2){ delete1(rt,x); }else if(opt==3){ printf("%d\n",queryRank(x)); }else if(opt==4){ printf("%d\n",queryKey(x)); }else if(opt==5){ printf("%d\n",queryQian(x)); }else if(opt==6){ printf("%d\n",queryHou(x)); } } }

 

转载于:https://www.cnblogs.com/wifimonster/p/10134830.html

相关资源：数据结构—成绩单生成器