bzoj 3224: Tyvj 1728 普通平衡树
Contents
3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
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>
#include<cstdlib>
#include<iostream>
using namespace std;
#define N 100010
inline int read()
{
int tmp=0,pp=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0';ch=getchar();}
return tmp*pp;
}
int op,x,ls[N],rs[N],w[N],a[N],siz[N],rnd[N],cnt,n,root,q,h;
inline void pu(int p){siz[p]=siz[ls[p]]+siz[rs[p]]+w[p];}
inline void lx(int &p)
{
int t=rs[p];
rs[p]=ls[t];
ls[t]=p;
pu(p);pu(t);
p=t;
}
inline void rx(int &p)
{
int t=ls[p];
ls[p]=rs[t];
rs[t]=p;
pu(p);pu(t);
p=t;
}
inline void cr(int &p,int v)
{
if(!p)
{
p=++cnt,a[p]=v,siz[p]=1,w[p]=1,rnd[p]=rand();
return;
}
if(v==a[p]) w[p]++;
else if(v<a[p])
{
cr(ls[p],v);
if(rnd[ls[p]]>rnd[p]) rx(p);
}
else
{
cr(rs[p],v);
if(rnd[rs[p]]>rnd[p]) lx(p);
}
pu(p);
}
inline void del(int &p,int v)
{
if(!p) return;
if(v==a[p])
{
if(w[p]>1) w[p]--;
else if(ls[p]*rs[p]==0) p=ls[p]+rs[p];
else if(rnd[ls[p]]>rnd[rs[p]]) rx(p),del(p,v);
else lx(p),del(p,v);
}
else if(v>a[p]) del(rs[p],v);
else del(ls[p],v);
pu(p);
}
inline int paim(int p,int v)
{
if(v==a[p]) return siz[ls[p]]+1;
else if(v>a[p]) return siz[ls[p]]+w[p]+paim(rs[p],v);
else return paim(ls[p],v);
}
inline int finx(int p,int v)
{
if(siz[ls[p]]>=v) return finx(ls[p],v);
else if(siz[ls[p]]+w[p]>=v) return a[p];
else return finx(rs[p],v-siz[ls[p]]-w[p]);
}
inline void qq(int p,int v)
{
if(!p) return;
else if(v>a[p])
{
q=a[p];
qq(rs[p],v);
}
else qq(ls[p],v);
}
inline void hj(int p,int v)
{
if(!p) return;
else if(v<a[p])
{
h=a[p];
hj(ls[p],v);
}
else hj(rs[p],v);
}
int main()
{
n=read();
while(n--)
{
op=read();x=read();
if(op==1) cr(root,x);
else if(op==2) del(root,x);
else if(op==3) printf("%d\n",paim(root,x));
else if(op==4) printf("%d\n",finx(root,x));
else if(op==5){qq(root,x);printf("%d\n",q);}
else {hj(root,x);printf("%d\n",h);}
}
}
发表评论