3685: 普通van Emde Boas树
Time Limit: 9 Sec Memory Limit: 128 MB
Submit: 962 Solved: 319
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
#include<cstdio>#include<iostream>using namespace std;int n,m;struct kx{int value;}node[4000001];int read(){int w=0,c=1; char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') c=-1;ch=getchar();}while (ch>='0' && ch<='9')w=w*10+ch-'0',ch=getchar();return w*c;}void build(int s,int l,int r){if (l==r) return;build(s*2,l,(l+r)/2),build(s*2+1,(l+r)/2+1,r);}int find(int s,int l,int r,int val){int mid=(l+r)/2;if (l==r)if (node[s].value) return 1;else return -1;if (val<=mid) return find(s*2,l,mid,val);else return find(s*2+1,mid+1,r,val);}void change(int s,int l,int r,int val){int mid=(l+r)/2;if (l==r) {node[s].value=1;return;}if (val<=mid) change(s*2,l,mid,val);else change(s*2+1,mid+1,r,val);node[s].value=node[s*2].value+node[s*2+1].value;}void del(int s,int l,int r,int val){int mid=(l+r)/2;if (l==r){node[s].value=0;return;}if (val<=mid) del(s*2,l,mid,val);else del(s*2+1,mid+1,r,val);node[s].value=node[s*2].value+node[s*2+1].value;}int querymin(int s,int l,int r){int mid=(l+r)/2;if (!node[s].value) return -1;if (l==r) return l;if (node[s*2].value) return querymin(s*2,l,mid);else return querymin(s*2+1,mid+1,r);}int querymax(int s,int l,int r){int mid=(l+r)/2;if (!node[s].value) return -1;if (l==r) return l;if (node[s*2+1].value) return querymax(s*2+1,mid+1,r);else return querymax(s*2,l,mid);}int querypred(int s,int l,int r,int val){int mid=(l+r)/2,t;if (val<0 || !node[s].value) return -1;if (l==r) return l;if (val<=mid) return querypred(s*2,l,mid,val);else{t=querypred(s*2+1,mid+1,r,val);if (t==-1) return querymax(s*2,l,mid);else return t;}}int querysucc(int s,int l,int r,int val){int mid=(l+r)/2,t;if (!node[s].value) return -1;if (l==r) return l;if (val>mid) return querysucc(s*2+1,mid+1,r,val);else{t=querysucc(s*2,l,mid,val);if (t==-1) return querymin(s*2+1,mid+1,r);else return t;}}int main(){int i,x,p;n=read(),m=read();build(1,0,n);for (i=1;i<=m;i++){p=read();if (p!=3 && p!=4) x=read();switch (p){case 1:if (find(1,0,n,x)==-1) change(1,0,n,x); break;case 2:if (find(1,0,n,x)==1) del(1,0,n,x); break;case 3:printf("%d\n",querymin(1,0,n)); break;case 4:printf("%d\n",querymax(1,0,n)); break;case 5:printf("%d\n",querypred(1,0,n,x-1)); break;case 6:printf("%d\n",querysucc(1,0,n,x+1)); break;case 7:printf("%d\n",find(1,0,n,x)); break;}}return 0;}
