题意：给定一个n个数的序列，多次询问，每次询问区间[l,r]的mex
直接暴力显然不可
区间[l,r]和区间[l',r']mex的情况：
（1）[l,r]和[l',r']的mex值不同：[l,r]的mex值在[l',r']中出现 或 原本在[l,r]中存在而不在[l',r']中存在从而成为[l',r']的mex值 （反之同理）
（2）[l,r]和[l',r']的mex值相同：区间内出现的元素相同或只有比mex值大的元素不同
类似莫队的思想，如果已知[l,r]的mex值，那么[l+1,r]的mex值会出现以下情况：
（1）与[l,r]的mex值相同
（2）[l+1,r]中没有出现元素a[l]且a[l]成为了[l',r']的mex值
也就是说，只需要找到a[l]下一次出现的位置p，并把[l,p-1]中所有sg值比a[l]大的全都替换成a[l]即可
如果直接修改会T，那么就可以利用线段树区间修改即可
那么我们就需要离线，按查询的左端点为第一关键字、右端点为第二关键字排序
线段树中，真正有用的只有叶子结点，建一棵完整的线段树只是为了存一下lazy...mex本身是不资磁合并的...
uses math; type rec=record mex:longint; end; type rec2=record l,r,id:longint; end; var n,m,tt :longint; i :longint; vis :array[0..200010] of boolean; sg,a,last,next :array[0..200010] of longint; q :array[0..200010] of rec2; ans :array[0..200010] of longint; t :array[0..600010] of rec; procedure sort(l,r:longint); var i,j,x,y:longint; z:rec2; begin i:=l; j:=r; x:=q[(l+r)>>1].l; y:=q[(l+r)>>1].r; while i<=j do begin while (q[i].l<x) or (q[i].l=x) and (q[i].r<y) do inc(i); while (q[j].l>x) or (q[j].l=x) and (q[j].r>y) do dec(j); if i<=j then begin z:=q[i]; q[i]:=q[j]; q[j]:=z; inc(i); dec(j); end; end; if i<r then sort(i,r); if j>l then sort(l,j); end; procedure build(x,l,r:longint); var mid:longint; begin if l=r then begin t[x].mex:=sg[l]; exit; end; mid:=(l+r)>>1; build(x<<1,l,mid); build((x<<1)+1,mid+1,r); t[x].mex:=maxlongint; end; procedure update(x,l,r:longint); begin if l=r then exit; t[x<<1].mex:=min(t[x<<1].mex,t[x].mex); t[(x<<1)+1].mex:=min(t[(x<<1)+1].mex,t[x].mex); t[x].mex:=maxlongint; end; function find(x,l,r,y:longint):longint; var mid:longint; begin if t[x].mex<>maxlongint then update(x,l,r); if (l=r) and (l=y) then exit(t[x].mex); mid:=(l+r)>>1; if y<=mid then exit(find(x<<1,l,mid,y)) else exit(find((x<<1)+1,mid+1,r,y)); end; procedure change(x,l,r,x1,x2,y:longint); var mid:longint; begin if (l=x1) and (r=x2) then begin t[x].mex:=min(t[x].mex,y); exit; end; if t[x].mex<>maxlongint then update(x,l,r); mid:=(l+r)>>1; if x2<=mid then change(x<<1,l,mid,x1,x2,y) else if x1>mid then change((x<<1)+1,mid+1,r,x1,x2,y) else begin change(x<<1,l,mid,x1,mid,y); change((x<<1)+1,mid+1,r,mid+1,x2,y); end; end; begin read(n,m); for i:=1 to n do begin read(a[i]); if last[a[i]]<>0 then next[last[a[i]]]:=i; last[a[i]]:=i; end; tt:=0; for i:=1 to n do begin vis[a[i]]:=true; while vis[tt] do inc(tt); sg[i]:=tt; end; build(1,1,n); // for i:=1 to m do read(q[i].l,q[i].r); for i:=1 to m do q[i].id:=i; sort(1,m); tt:=1; for i:=1 to m do begin while q[i].l>tt do begin if next[tt]=0 then next[tt]:=n+1; change(1,1,n,tt,next[tt]-1,a[tt]); inc(tt); end; ans[q[i].id]:=find(1,1,n,q[i].r); end; for i:=1 to m do writeln(ans[i]); end. ——by Eirlys
