Description
Input
Output
Sample Input
7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
Sample Output
3
0
3
2
4
0
3
2
4
HINT
Source
By Xhr
Solution
莫队。
|
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 |
#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) { num[a[x]]--; if (!num[a[x]]) ans=min(ans,a[x]); } void change2(int x) { 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; 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; } |
