【原题题面】传送门
【题解大意】
都说了是莫队练习题。
考虑已知[l,r]区间的mex值时，如何求[l+1,r]的mex值。
比较a[l+1]与已知ans的大小，如果a[l+1]>ans或者a[l+1]<ans，均对答案没有影响。
如果a[l+1]==ans，考虑找到一个比当前ans更大且出现次数为0的点。
其余的区间扩展亦同理。
交上去的代码一直WA，各路神仙路过请帮忙看下，谢谢！
【code】
#include<bits/stdc++.h> using namespace std; #define File "testdata" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".ans","w",stdout); } 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<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f; } const int mxn = 2e5+5; int n,m,Block; int a[mxn],cnt[mxn],ans[mxn]; struct Q{ int l,r,id; }q[mxn]; inline bool cmp1(Q x,Q y){ if((x.l/Block)^(y.l/Block)) return x.l < y.l; else if((x.l/Block)&1) return x.r < y.r; return x.r > y.r; } int answer = 0; inline void mov1(int x){ cnt[a[x]] ++; if(cnt[a[x]]==1 && answer==a[x]){ int t = a[x]; while(++t && !cnt[t]){ answer = t; return; } } }//add inline void mov2(int x){ cnt[a[x]] --; if(answer>a[x] && !cnt[a[x]]){ answer = a[x]; return; } }//del int main(){ // file(); n = read(),m = read(); for(int i = 1;i <= n; ++i) a[i] = read(); for(int i = 1;i <= m; ++i) q[i].l = read(),q[i].r = read(),q[i].id = i; Block = (int)sqrt(n); int l(1),r(0); sort(q+1,q+m+1,cmp1); for(int i = 1;i <= m; ++i){ int ql = q[i].l,qr = q[i].r; while(ql < l) mov1(l-1),l--; while(ql > l) mov2(l),l++; while(qr > r) mov1(r+1),r++; while(qr < r) mov2(r),r--; ans[q[i].id] = answer; } for(int i = 1;i <= m; ++i) printf("%d ",ans[i]); return 0; } /* 5 5 2 1 0 2 1 3 3 2 3 2 4 1 2 3 5 */