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
By 佚名提供
Solution
莫队，可以发现如果值大于n那么是对答案没有影响的，所以不用离散化，直接忽略即可。
然后此题和BZOJ3339: Rmq Problem相同。
这题在写莫队时要先进后出，即代码中先进行change2，再进行change1。
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,q,a[200100],block[200100],ans,num[200010],answer[200100]; struct node{int l,r,tot;}x[200100]; bool cmp(node a,node b) { if (block[a.l]==block[b.l]) return block[a.r]<block[b.r]; return block[a.l]<block[b.l]; } void change1(int x) { if (a[x]>n) return; num[a[x]]--; if (!num[a[x]]) ans=min(ans,a[x]); } void change2(int x) { if (a[x]>n) return; num[a[x]]++; if (a[x]==ans) while (num[ans]) ans++; } int main() { scanf("%d%d",&n,&q); int blo=(int)sqrt(n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),block[i]=(i-1)/blo+1; for (int i=1;i<=q;i++) scanf("%d%d",&x[i].l,&x[i].r),x[i].tot=i; sort(x+1,x+q+1,cmp); int l=1,r=1; ans=(a[1]==0)?1:0; if (a[1]<=n) num[a[1]]=1; for (int i=1;i<=q;i++) { while (l>x[i].l) l--,change2(l); while (r>x[i].r) change1(r),r--; while (r<x[i].r) r++,change2(r); while (l<x[i].l) change1(l),l++; answer[x[i].tot]=ans; } for (int i=1;i<=q;i++) printf("%d\n",answer[i]); return 0; } |
