「BZOJ3685」普通van Emde Boas树
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
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
题解
线段树写的又慢又长
给会zkw线段树的跪了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; struct seg{int l,r,v;}t[3000005]; void build(int k,int l,int r) { t[k].l=l;t[k].r=r; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } int mn(int k) { if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; if(t[k<<1].v)return mn(k<<1); else return mn(k<<1|1); } int mx(int k) { if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; if(t[k<<1|1].v)return mx(k<<1|1); else return mx(k<<1); } void insert(int k,int val) { int l=t[k].l,r=t[k].r; if(l==r){t[k].v=1;return;} int mid=(l+r)>>1; if(val<=mid)insert(k<<1,val); else insert(k<<1|1,val); t[k].v=t[k<<1].v+t[k<<1|1].v; } int find(int k,int val) { int l=t[k].l,r=t[k].r; if(l==r) { if(t[k].v)return 1; return -1; } int mid=(l+r)>>1; if(val<=mid)return find(k<<1,val); else return find(k<<1|1,val); } void del(int k,int val) { int l=t[k].l,r=t[k].r; if(l==r){t[k].v=0;return;} int mid=(l+r)>>1; if(val<=mid)del(k<<1,val); else del(k<<1|1,val); t[k].v=t[k<<1].v+t[k<<1|1].v; } int findpr(int k,int val) { if(val<0)return -1; if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; int mid=(l+r)>>1; if(val<=mid)return findpr(k<<1,val); else { int t=findpr(k<<1|1,val); if(t==-1)return mx(k<<1); else return t; } } int findsu(int k,int val) { if(!t[k].v)return -1; int l=t[k].l,r=t[k].r; if(l==r)return l; int mid=(l+r)>>1; if(val>mid)return findsu(k<<1|1,val); else { int t=findsu(k<<1,val); if(t==-1)return mn(k<<1|1); else return t; } } int main() { n=read();m=read(); build(1,0,n); int opt,x; for(int i=1;i<=m;i++) { opt=read(); switch(opt) { case 1:x=read();if(find(1,x)==-1)insert(1,x);break; case 2:x=read();if(find(1,x)==1)del(1,x);break; case 3:printf("%d\n",mn(1));break; case 4:printf("%d\n",mx(1));break; case 5:x=read();printf("%d\n",findpr(1,x-1));break; case 6:x=read();printf("%d\n",findsu(1,x+1));break; case 7:x=read();printf("%d\n",find(1,x));break; } } return 0; } |
计数器 9320680
OI 课件=>
OI 课件=>
对于
4 2
1 4
6 4
我觉得结果应该是-1啊，您的程序给出的似乎是4，还是我SB了
T T 不懂
4应该没有后继了吧
zkw又好写又快233
神犇不要再D我了。。