【原题题面】

【题解大意】

都说了是莫队练习题。

考虑已知[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
      
       using namespace std;#define File "testdata"#define ll long longinline 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;        }    }}//addinline void mov2(int x){    cnt[a[x]] --;    if(answer>a[x] && !cnt[a[x]]){        answer = a[x];        return;    }}//delint 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\n",ans[i]);    return 0;}/*5 52 1 0 2 13 32 32 41 23 5*/