「BZOJ3585」mex
Description
有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
Input
第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。
Output
一行一个数，表示每个询问的答案。
Sample Input
5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
2
3
0
3
HINT
数据规模和约定
对于100%的数据：
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据：
1<=n,m<=1000
Source
此题为bzoj3339的升级版。。
区别就在于此题需要离散化
然后就没了。。。
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #define inf 0x7fffffff using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,cnt,k=0; int a[200005],b[200005],sg[200005],ans[200005],next[200005],last[200005]; int ls[600005],rs[600005],mn[600005]; bool mark[200005]; struct data{int l,r,id;}q[200005]; bool cmp(data a,data b) {return a.l<b.l;} int find(int x) { int l=1,r=cnt; while(l<=r) { int mid=(l+r)>>1; if(b[mid]<x)l=mid+1; else r=mid-1; } return l; } void build(int k,int l,int r) { ls[k]=l;rs[k]=r;mn[k]=inf; if(l==r){mn[k]=sg[l];return;} int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void pushdown(int k) { int l=ls[k],r=rs[k]; if(l==r)return; mn[k<<1]=min(mn[k],mn[k<<1]); mn[k<<1|1]=min(mn[k],mn[k<<1|1]); } int ask(int k,int x) { if(mn[k]!=inf)pushdown(k); int l=ls[k],r=rs[k]; if(l==r)return mn[k]; int mid=(l+r)>>1; if(x<=mid)return ask(k<<1,x); return ask(k<<1|1,x); } void update(int k,int x,int y,int val) { if(mn[k]!=inf)pushdown(k); int l=ls[k],r=rs[k]; if(l==x&&y==r){mn[k]=min(mn[k],val);return;} int mid=(l+r)>>1; if(y<=mid)update(k<<1,x,y,val); else if(x>mid)update(k<<1|1,x,y,val); else {update(k<<1,x,mid,val);update(k<<1|1,mid+1,y,val);} } int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=b[i]=read(); sort(b+1,b+n+1); for(int i=1;i<=n;i++) if(b[i]!=b[i-1]||i==1)b[++cnt]=b[i]; for(int i=1;i<=n;i++) { int t=find(a[i]); mark[t]=1; if(a[i]==k) while(mark[t]) { k++; if(b[++t]!=k)break; } sg[i]=k; } build(1,1,n); for(int i=n;i>0;i--) next[i]=last[find(a[i])],last[find(a[i])]=i; for(int i=1;i<=m;i++) { q[i].l=read();q[i].r=read(); q[i].id=i; } sort(q+1,q+m+1,cmp); int now=1; for(int i=1;i<=m;i++) { while(now<q[i].l) { if(!next[now])next[now]=n+1; update(1,now,next[now]-1,a[now]); now++; } ans[q[i].id]=ask(1,q[i].r); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; } |
Subscribe
计数器 9862409
OI 课件=>
OI 课件=>