普通van Emde Boas树
Time Limit: 9 Sec Memory Limit: 128 MB
Submit: 1969 Solved: 639
[Submit][Status][Discuss]
Description
设计数据结构支持:
1 x 若x不存在,插入x
2 x 若x存在,删除x
3 输出当前最小值,若不存在输出-1
4 输出当前最大值,若不存在输出-1
5 x 输出x的前驱,若不存在输出-1
6 x 输出x的后继,若不存在输出-1
7 x 若x存在,输出1,否则输出-1
Input
第一行给出n,m 表示出现数的范围和操作个数
接下来m行给出操作
n<=10^6,m<=2*10^6,0<=x<n
Output
Sample Input
10 11
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2
Sample Output
1
-1
2
2
2
-1
-1
2
2
2
-1
HINT
Source
题解：
很多数据结构都可以解决。
权值线段树就可以。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> #define N 3000007 using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} int n,m;
struct seg
{
int l,r,v;
}t[N]; void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;
if(l==r)return;
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
}
int mn(int k)
{
if(!t[k].v)return -;
int l=t[k].l,r=t[k].r;
if(l==r)return l;
if(t[k<<].v)return mn(k<<);
else return mn(k<<|);
}
int mx(int k)
{
if(!t[k].v)return -;
int l=t[k].l,r=t[k].r;
if(l==r)return l;
if(t[k<<|].v)return mx(k<<|);
else return mx(k<<);
}
void insert(int k,int val)
{
int l=t[k].l,r=t[k].r;
if(l==r){t[k].v=;return;}
int mid=(l+r)>>;
if(val<=mid)insert(k<<,val);
else insert(k<<|,val);
t[k].v=t[k<<].v+t[k<<|].v;
}
int find(int k,int val)
{
int l=t[k].l,r=t[k].r;
if(l==r)
{
if(t[k].v)return ;
return -;
}
int mid=(l+r)>>;
if(val<=mid)return find(k<<,val);
else return find(k<<|,val);
}
void del(int k,int val)
{
int l=t[k].l,r=t[k].r;
if(l==r){t[k].v=;return;}
int mid=(l+r)>>;
if(val<=mid)del(k<<,val);
else del(k<<|,val);
t[k].v=t[k<<].v+t[k<<|].v;
}
int findpr(int k,int val)
{
if(val<)return -;
if(!t[k].v)return -;
int l=t[k].l,r=t[k].r;
if(l==r)return l;
int mid=(l+r)>>;
if(val<=mid)return findpr(k<<,val);
else
{
int t=findpr(k<<|,val);
if(t==-)return mx(k<<);
else return t;
}
}
int findsu(int k,int val)
{
if(!t[k].v)return -;
int l=t[k].l,r=t[k].r;
if(l==r)return l;
int mid=(l+r)>>;
if(val>mid)return findsu(k<<|,val);
else
{
int t=findsu(k<<,val);
if(t==-)return mn(k<<|);
else return t;
}
}
int main()
{
n=read(),m=read();
build(,,n);
int opt,x;
for(int i=;i<=m;i++)
{
opt=read();
switch(opt)
{
case :x=read();if(find(,x)==-)insert(,x);break;
case :x=read();if(find(,x)==)del(,x);break;
case :printf("%d\n",mn());break;
case :printf("%d\n",mx());break;
case :x=read();printf("%d\n",findpr(,x-));break;
case :x=read();printf("%d\n",findsu(,x+));break;
case :x=read();printf("%d\n",find(,x));break;
}
}
}