3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 11427 Solved: 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
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
数据如下http://pan.baidu.com/s/1jHMJwO2
Source
#include <cstdio>
#define Maxn 1000000
using namespace std;
int f[Maxn];//father
int ch[Maxn][];//child ; 0 for left ; 1 for right
int key[Maxn];//key
int cnt[Maxn];//value
int siz[Maxn];//size of subtree
int sz,root;//size of tree and root
//clear the ndoe void clear(int x)
{
ch[x][]=ch[x][]=f[x]=cnt[x]=key[x]=siz[x]=;
} //rightson return 1;left son return 0
int getson(int x)
{
return ch[f[x]][]==x;
} //update the size
void update(int x)
{
siz[x]=cnt[x];
if (ch[x][]) siz[x]+=siz[ch[x][]];
if (ch[x][]) siz[x]+=siz[ch[x][]];
} //retation
int rotate(int x)
{
int fa=f[x],fafa=f[fa],k=getson(x);
ch[fa][k]=ch[x][k^];f[ch[fa][k]]=fa;
ch[x][k^]=fa;f[fa]=x;
f[x]=fafa;
if (fafa)
ch[fafa][ch[fafa][]==fa]=x;
update(fa);update(x);
} //rotate until x is the root
void 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][];
while(ch[now][])
now=ch[now][];
return now;
} int nex()
{
int now=ch[root][];
while(ch[now][])
now=ch[now][];
return now;
} //find x's pos
int findpos(int v)
{
int now=root,ans=;
while()
{
if (v<key[now])
now=ch[now][];
else
{
ans+=ch[now][]?siz[ch[now][]]:;
if (v==key[now])
{
splay(now);
return ans+;
}
ans+=cnt[now];
now=ch[now][];
}
}
} //find pos's x
int findx(int x)
{
int now=root;
while()
{
if (ch[now][] && x<=siz[ch[now][]])
now=ch[now][];
else
{
int temp=(ch[now][]?siz[ch[now][]]:)+cnt[now];
if (x<=temp)
return key[now];
x-=temp;
now=ch[now][];
}
}
} //ceate a new splay node
void create(int v)
{
sz++;
ch[sz][]=ch[sz][]=f[sz]=;
key[sz]=v;
cnt[sz]=;
siz[sz]=;
//root=sz;
} //insert a node
void insert(int v)
{
if (!root)
create(v),root=sz;
else
{
int now=root,fa=;
while()
{
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]>)
{
cnt[root]--;
update(root);
return;
}
//none
if (!ch[root][] && !ch[root][])
{
clear(root);
root=;
return;
}
//one
if (!ch[root][])
{
int temp=root;
root=ch[root][];
f[root]=;
clear(temp);
return;
}
else
if (!ch[root][])
{
int temp=root;
root=ch[root][];
f[root]=;
clear(temp);
return;
}
//two
int pre1=pre(),temp=root;
splay(pre1);
f[ch[temp][]]=root;
ch[root][]=ch[temp][];
clear(temp);
update(root);
} int main()
{
int n,opt,x;
scanf("%d",&n);
for (int i=;i<=n;++i)
{
scanf("%d%d",&opt,&x);
switch(opt)
{
case : insert(x); break;
case : del(x); break;
case : printf("%d\n",findpos(x)); break;
case : printf("%d\n",findx(x)); break;
case : insert(x); printf("%d\n",key[pre()]); del(x); break;
case : insert(x); printf("%d\n",key[nex()]); del(x); break;
}
}
}
#include<iostream>
#include<cstdio>
#include<cstring> #define N 1000000 using namespace std;
int f[N],ch[N][],key[N],cnt[N],siz[N],sz,root; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void update(int x)
{
siz[x]=cnt[x];
if(ch[x][]) siz[x]+=siz[ch[x][]];
if(ch[x][]) siz[x]+=siz[ch[x][]];
} int pre()
{
int now=ch[root][];
while(ch[now][]) now=ch[now][];return now;
} int nex()
{
int now=ch[root][];
while(ch[now][]) now=ch[now][];return now;
} inline int getson(int x)
{
return ch[f[x]][]==x;
} inline void rorate(int x)
{
int fa=f[x],ffa=f[fa],k=getson(x);
ch[fa][k]=ch[x][k^];f[ch[fa][k]]=fa;
ch[x][k^]=fa;f[fa]=x;f[x]=ffa;
if(ffa)ch[ffa][ch[ffa][]==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=;
while()
{
if(x<key[now]) now=ch[now][];
else
{
ans+=ch[now][]?siz[ch[now][]]:;
if(x==key[now])
{
splay(now);return ans+;
}
ans+=cnt[now];now=ch[now][];
}
}
} int findx(int x)
{
int now=root;
while()
{
if(ch[now][]&&x<=siz[ch[now][]]) now=ch[now][];
else
{
int tmp=(ch[now][]?siz[ch[now][]]:)+cnt[now];
if(x<=tmp) return key[now];
x-=tmp;now=ch[now][];
}
}
} void clear(int x)
{
ch[x][]=ch[x][]=cnt[x]=siz[x]=key[x]=f[x]=;
} void creat(int x)
{
sz=sz+;key[sz]=x;cnt[sz]=siz[sz]=;
ch[sz][]=ch[sz][]=f[sz]=;
} void insert(int x)
{
if(!root) creat(x),root=sz;
else
{
int now=root,fa=;
while()
{
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]>)
{
cnt[root]--;siz[root]--;return;
}
if(!ch[root][]&&!ch[root][])
{
clear(root);root=;return;
}
if(!ch[root][])
{
int tmp=root;root=ch[root][];f[root]=;
clear(tmp);return;
}
if(!ch[root][])
{
int tmp=root;root=ch[root][];f[root]=;
clear(tmp);return;
}
int pre1=pre(),tmp=root;splay(pre1);
ch[root][]=ch[tmp][];f[ch[tmp][]]=root;
clear(tmp);update(root);
} int main()
{
int n,opt,x;
n=read();
for(int i=;i<=n;i++)
{
opt=read();x=read();
switch(opt)
{
case :insert(x);break;
case :del(x);break;
case :printf("%d\n",findpos(x));break;
case :printf("%d\n",findx(x));break;
case :insert(x);printf("%d\n",key[pre()]);del(x);break;
case :insert(x);printf("%d\n",key[nex()]);del(x);break;
}
}
}
我的马蜂