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.每个数的数据范围:[-2e9,2e9]
Source
STL用法练手题。。。(手动滑稽)
这数据我给满分
(感谢hzwer...)
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
rg int x=,f=;rg char ch=getchar();
while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
vector<int>A;
int main(){
int n=gi(),opt,x;
while(n--){
opt=gi(),x=gi();
if(opt==)A.insert(upper_bound(A.begin(),A.end(),x),x);
else if(opt==)A.erase(lower_bound(A.begin(),A.end(),x));
else if(opt==)printf("%d\n",lower_bound(A.begin(),A.end(),x)-A.begin()+);
else if(opt==)printf("%d\n",A[x-]);
else if(opt==)printf("%d\n",*(lower_bound(A.begin(),A.end(),x)-));
else printf("%d\n",*upper_bound(A.begin(),A.end(),x));
}
return ;
}
(学习treap中,到时候再发)
更新:
液我A了!!!
先上代码
// It is made by XZZ
#include<cstdio>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define Ls tree[now].ls
#define Rs tree[now].rs
typedef long long ll;
il int gi(){
rg int x=,f=;rg char ch=getchar();
while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
struct node{
int ls,rs,value,rand,sum,size;
node(){ls=rs=value=rand=sum=size=;}
}tree[];
int root=,siz=;
ll seed=;
il int Rand(){return seed=seed*48271LL%;}
il vd reset(int now){
tree[now].size=tree[Ls].size+tree[Rs].size+tree[now].sum;
}
il vd lrot(int&now){
int ls=tree[now].ls;
tree[now].ls=tree[ls].rs,tree[ls].rs=now;
tree[ls].size=tree[now].size;reset(now);now=ls;
}
il vd rrot(int&now){
int rs=tree[now].rs;
tree[now].rs=tree[rs].ls,tree[rs].ls=now;
tree[rs].size=tree[now].size;reset(now);now=rs;
}
il vd ins(int&now,int num){
if(now==){
++siz,now=siz,tree[now].size=tree[now].sum=,tree[now].value=num,tree[now].rand=Rand();
return;
}
++tree[now].size;
if(tree[now].value==num)++tree[now].sum;
else if(num<tree[now].value){
ins(Ls,num);
if(tree[Ls].rand<tree[now].rand)lrot(now);
}else{
ins(Rs,num);
if(tree[Rs].rand<tree[now].rand)rrot(now);
}
}
il vd del(int&now,int num){
if(now==)return;
if(tree[now].value==num){
if(tree[now].sum>){--tree[now].sum,--tree[now].size;return;}
if(!Ls||!Rs)now=Ls|Rs;
else if(tree[Ls].rand<tree[Rs].rand)lrot(now),del(now,num);
else rrot(now),del(now,num);
return;
}
--tree[now].size;
if(num<tree[now].value)del(Ls,num);
else del(Rs,num);
}
il int getrank(int now,int num){
if(now==)return ;
if(tree[now].value==num)return tree[Ls].size+;
if(num>tree[now].value)return tree[Ls].size+tree[now].sum+getrank(Rs,num);
else return getrank(Ls,num);
}
il int getnum(int now,int num){
if(num<=tree[Ls].size)return getnum(Ls,num);
else if(num>tree[Ls].size+tree[now].sum)return getnum(Rs,num-tree[Ls].size-tree[now].sum);
else return tree[now].value;
}
int ans;
il vd lower(int now,int num){
if(now==)return;
if(tree[now].value<num)ans=now,lower(Rs,num);
else lower(Ls,num);
}
il vd upper(int now,int num){
if(now==)return;
if(tree[now].value>num)ans=now,upper(Ls,num);
else upper(Rs,num);
}
int main(){
int n=gi(),opt,x;
while(n--){
opt=gi(),x=gi();
switch(opt){
case :ins(root,x);break;
case :del(root,x);break;
case :printf("%d\n",getrank(root,x));break;
case :printf("%d\n",getnum(root,x));break;
case :ans=,lower(root,x),printf("%d\n",tree[ans].value);break;
case :ans=,upper(root,x),printf("%d\n",tree[ans].value);break;
}
}
return ;
}
因为太短了,写一点东西。。。
treap==tree+heap
因为二叉查找树很难平衡,所以加一个随机权值,当作一个堆维护
所以treap既有tree性质又有heap性质
当heap性质被破坏后用旋转来维护
我们还可以把函数写成非递归的。。。
// It is made by XZZ
#include<cstdio>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define Ls tree[now].ls
#define Rs tree[now].rs
typedef long long ll;
il int gi(){
rg int x=,f=;rg char ch=getchar();
while(ch<''||ch>'')f=ch=='-'?-:f,ch=getchar();
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
struct node{
int ls,rs,value,rand,sum,size;
node(){ls=rs=value=rand=sum=size=;}
}tree[];
int root=,siz=;
ll seed=;
il int Rand(){return seed=seed*48271LL%;}
il vd reset(int now){
tree[now].size=tree[Ls].size+tree[Rs].size+tree[now].sum;
}
il vd lrot(int&now){
int ls=tree[now].ls;
tree[now].ls=tree[ls].rs,tree[ls].rs=now;
tree[ls].size=tree[now].size;reset(now);now=ls;
}
il vd rrot(int&now){
int rs=tree[now].rs;
tree[now].rs=tree[rs].ls,tree[rs].ls=now;
tree[rs].size=tree[now].size;reset(now);now=rs;
}
il vd ins(int&now,int num){
if(now==){
++siz,now=siz,tree[now].size=tree[now].sum=,tree[now].value=num,tree[now].rand=Rand();
return;
}
++tree[now].size;
if(tree[now].value==num)++tree[now].sum;
else if(num<tree[now].value){
ins(Ls,num);
if(tree[Ls].rand<tree[now].rand)lrot(now);
}else{
ins(Rs,num);
if(tree[Rs].rand<tree[now].rand)rrot(now);
}
}
il vd del(int&now,int num){
if(now==)return;
if(tree[now].value==num){
if(tree[now].sum>){--tree[now].sum,--tree[now].size;return;}
if(!Ls||!Rs)now=Ls|Rs;
else if(tree[Ls].rand<tree[Rs].rand)lrot(now),del(now,num);
else rrot(now),del(now,num);
return;
}
--tree[now].size;
if(num<tree[now].value)del(Ls,num);
else del(Rs,num);
}
il int getrank(int now,int num){
int Rank=;
while(now)if(tree[now].value==num)return tree[Ls].size++Rank;
else if(num>tree[now].value)Rank+=tree[Ls].size+tree[now].sum,now=Rs;
else now=Ls;
}
il int getnum(int now,int num){
while()
if(num<=tree[Ls].size)now=Ls;
else if(num>tree[Ls].size+tree[now].sum)num-=tree[Ls].size+tree[now].sum,now=Rs;
else return tree[now].value;
}
il int lower(int now,int num){
int ret;
while(now)if(tree[now].value<num)ret=tree[now].value,now=Rs;
else now=Ls;
return ret;
}
il int upper(int now,int num){
int ret;
while(now)if(tree[now].value>num)ret=tree[now].value,now=Ls;
else now=Rs;
return ret;
}
int main(){
freopen("phs.in","r",stdin);
freopen("phs.out","w",stdout);
int n=gi(),opt,x;
while(n--){
opt=gi(),x=gi();
switch(opt){
case :ins(root,x);break;
case :del(root,x);break;
case :printf("%d\n",getrank(root,x));break;
case :printf("%d\n",getnum(root,x));break;
case :printf("%d\n",lower(root,x));break;
case :printf("%d\n",upper(root,x));break;
}
}
return ;
}
这样在cogs上可以从1.90s下降到1.70s
在洛谷上可以从164ms上升到259ms(大雾)
在bzoj上可以从300ms下降到296ms
所以非递归到底有没有用???