3224: Tyvj 1728 普通平衡树
Time Limit:10 SecMemory Limit:128 MBSubmit:11427Solved:4878
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
101 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
10646584185
492737
HINT
1.n的数据范围：n<=1000002.每个数的数据范围：[-1e7,1e7]
数据如下/s/1jHMJwO2
Source
平衡树
#include <cstdio>#define Maxn 1000000using namespace std;int f[Maxn];//fatherint ch[Maxn][2];//child ; 0 for left ; 1 for rightint key[Maxn];//keyint cnt[Maxn];//valueint siz[Maxn];//size of subtreeint sz,root;//size of tree and root//clear the ndoevoid clear(int x){ch[x][0]=ch[x][1]=f[x]=cnt[x]=key[x]=siz[x]=0;}//rightson return 1;left son return 0int getson(int x){return ch[f[x]][1]==x;}//update the sizevoid update(int x){siz[x]=cnt[x];if (ch[x][0]) siz[x]+=siz[ch[x][0]];if (ch[x][1]) siz[x]+=siz[ch[x][1]];}//retationint rotate(int x){int fa=f[x],fafa=f[fa],k=getson(x);ch[fa][k]=ch[x][k^1];f[ch[fa][k]]=fa;ch[x][k^1]=fa;f[fa]=x;f[x]=fafa;if (fafa)ch[fafa][ch[fafa][1]==fa]=x;update(fa);update(x);}//rotate until x is the rootvoid splay(int x){for (int fa;fa=f[x];rotate(x))if (f[fa])rotate(getson(x)==getson(fa) ? fa : x);root=x;}int pre(){int now=ch[root][0];while(ch[now][1])now=ch[now][1];return now;}int nex(){int now=ch[root][1];while(ch[now][0])now=ch[now][0];return now;}//find x's posint findpos(int v){int now=root,ans=0;while(1){if (v<key[now])now=ch[now][0];else{ans+=ch[now][0]?siz[ch[now][0]]:0;if (v==key[now]) {splay(now);return ans+1;}ans+=cnt[now];now=ch[now][1];}}}//find pos's xint findx(int x){int now=root;while(1){if (ch[now][0] && x<=siz[ch[now][0]])now=ch[now][0];else{int temp=(ch[now][0]?siz[ch[now][0]]:0)+cnt[now];if (x<=temp)return key[now];x-=temp;now=ch[now][1];}}}//ceate a new splay nodevoid create(int v){sz++;ch[sz][0]=ch[sz][1]=f[sz]=0;key[sz]=v;cnt[sz]=1;siz[sz]=1;//root=sz;}//insert a nodevoid insert(int v){if (!root)create(v),root=sz;else{int now=root,fa=0;while(1){if (key[now]==v){cnt[now]++;update(now);update(fa);splay(now);break;}fa=now;now=ch[fa][v>key[fa]];if (!now){create(v);f[sz]=fa;ch[fa][v>key[fa]]=sz;update(fa);splay(sz);break;}}}}void del(int x){int t=findpos(x);if (cnt[root]>1) {cnt[root]--;update(root);return;}//noneif (!ch[root][0] && !ch[root][1]){clear(root);root=0;return;}//oneif (!ch[root][1]){int temp=root;root=ch[root][0];f[root]=0;clear(temp);return;}elseif (!ch[root][0]){int temp=root;root=ch[root][1];f[root]=0;clear(temp);return;}//twoint pre1=pre(),temp=root;splay(pre1);f[ch[temp][1]]=root;ch[root][1]=ch[temp][1];clear(temp);update(root);}int main(){ int n,opt,x; scanf("%d",&n); for (int i=1;i<=n;++i){ scanf("%d%d",&opt,&x); switch(opt){ case 1: insert(x); break; case 2: del(x); break; case 3: printf("%d\n",findpos(x)); break; case 4: printf("%d\n",findx(x)); break; case 5: insert(x); printf("%d\n",key[pre()]); del(x); break;case 6: insert(x); printf("%d\n",key[nex()]); del(x); break;} } }
#include<iostream>#include<cstdio>#include<cstring>#define N 1000000using namespace std;int f[N],ch[N][2],key[N],cnt[N],siz[N],sz,root;inline int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;}inline void update(int x){siz[x]=cnt[x];if(ch[x][0]) siz[x]+=siz[ch[x][0]];if(ch[x][1]) siz[x]+=siz[ch[x][1]];}int pre(){int now=ch[root][0];while(ch[now][1]) now=ch[now][1];return now;}int nex(){int now=ch[root][1];while(ch[now][0]) now=ch[now][0];return now;}inline int getson(int x){return ch[f[x]][1]==x;}inline void rorate(int x){int fa=f[x],ffa=f[fa],k=getson(x);ch[fa][k]=ch[x][k^1];f[ch[fa][k]]=fa;ch[x][k^1]=fa;f[fa]=x;f[x]=ffa;if(ffa)ch[ffa][ch[ffa][1]==fa]=x;update(fa);update(x);}void splay(int x){for(int fa;fa=f[x];rorate(x))if(f[fa]) rorate(getson(x)==getson(fa)?fa:x);root=x;}int findpos(int x){int now=root,ans=0;while(1){if(x<key[now]) now=ch[now][0];else {ans+=ch[now][0]?siz[ch[now][0]]:0;if(x==key[now]){splay(now);return ans+1;}ans+=cnt[now];now=ch[now][1];}}}int findx(int x){int now=root;while(1){if(ch[now][0]&&x<=siz[ch[now][0]]) now=ch[now][0];else{int tmp=(ch[now][0]?siz[ch[now][0]]:0)+cnt[now];if(x<=tmp) return key[now];x-=tmp;now=ch[now][1];}}}void clear(int x){ch[x][0]=ch[x][1]=cnt[x]=siz[x]=key[x]=f[x]=0;}void creat(int x){sz=sz+1;key[sz]=x;cnt[sz]=siz[sz]=1;ch[sz][0]=ch[sz][1]=f[sz]=0;}void insert(int x){if(!root) creat(x),root=sz;else{int now=root,fa=0;while(1){if(key[now]==x){cnt[now]++;siz[now]++;splay(now);break;}fa=now;now=ch[fa][x>key[fa]];if(!now){creat(x);f[sz]=fa;ch[fa][x>key[fa]]=sz;splay(sz);break;}}}}void del(int x){int t=findpos(x);if(cnt[root]>1){cnt[root]--;siz[root]--;return;}if(!ch[root][0]&&!ch[root][1]){clear(root);root=0;return;}if(!ch[root][0]){int tmp=root;root=ch[root][1];f[root]=0;clear(tmp);return;}if(!ch[root][1]){int tmp=root;root=ch[root][0];f[root]=0;clear(tmp);return;}int pre1=pre(),tmp=root;splay(pre1);ch[root][1]=ch[tmp][1];f[ch[tmp][1]]=root;clear(tmp);update(root);}int main(){int n,opt,x;n=read();for(int i=1;i<=n;i++){opt=read();x=read();switch(opt){case 1 :insert(x);break;case 2 :del(x);break; case 3 :printf("%d\n",findpos(x));break;case 4 :printf("%d\n",findx(x));break;case 5 :insert(x);printf("%d\n",key[pre()]);del(x);break;case 6 :insert(x);printf("%d\n",key[nex()]);del(x);break; }}}
我的马蜂
