两题本质是一样，只不过3585要离散化
这种不修改，不强制的问题，显然先考虑离线算法这道题的思路和bzoj1878非常像考虑到如果只是求每个前缀的mex，我们是很容易扫一遍就得出来的我们设为这个位置的mex考虑从左往右依次删除当前数会对后面产生什么影响我们设删除数a[i],a[i]下一个相同数的位置为next[a[i]]显然对于[i+1,next[a[i]]-1]这些位置的mex可能有影响（如过没有next，就说明对后面所有位置都可能有影响）;凡是大于a[i]的一律都变成了a[i]因此我们考虑对每个询问按左端点排序然后从左往右依次删除a[i](按上述对后面位置进行修改)不难发现，当某个询问左端点=当前位置i时(当然是先查询后删除了），这个询问的答案就是右端点上的mex，显然修改操作我们可以用线段树来维护，这样就解决了这个问题
1 const inf=500010; 2 var loc,ans,next,last,sg,p,q,c,a,b:array[0..200010] of longint; 3 tree:array[0..800010] of longint; 4 d:array[0..400010] of longint; 5 v:array[0..400010] of boolean; 6 i,n,m,j,t,k:longint; 7 8 procedure swap(var a,b:longint); 9 var c:longint; 10 begin 11 c:=a; 12 a:=b; 13 b:=c; 14 end; 15 16 function min(a,b:longint):longint; 17 begin 18 if a>b then exit(b) else exit(a); 19 end; 20 21 function find(x:longint):longint; 22 var l,r,m:longint; 23 begin 24 l:=1; 25 r:=t; 26 while l<=r do 27 begin 28 m:=(l+r) shr 1; 29 if d[m]=x then exit(m); 30 if d[m]>x then r:=m-1 else l:=m+1; 31 end; 32 end; 33 34 procedure sort1(l,r:longint); 35 var i,j,x,y: longint; 36 begin 37 i:=l; 38 j:=r; 39 x:=p[(l+r) div 2]; 40 repeat 41 while p[i]j) then 44 begin 45 swap(p[i],p[j]); 46 swap(q[i],q[j]); 47 swap(c[i],c[j]); 48 inc(i); 49 j:=j-1; 50 end; 51 until i>j; 52 if l j) then 66 begin 67 swap(b[i],b[j]); 68 inc(i); 69 j:=j-1; 70 end; 71 until i>j; 72 if l =r) then100 tree[i]:=min(tree[i],z)101 else begin102 if tree[i]<>inf then push(i);103 m:=(l+r) shr 1;104 if x<=m then work(i*2,l,m,x,y,z);105 if y>m then work(i*2+1,m+1,r,x,y,z);106 end;107 end;108 109 function ask(i,l,r,x:longint):longint;110 var m:longint;111 begin112 if l=r then exit(tree[i])113 else begin114 if tree[i]<>inf then push(i);115 m:=(l+r) shr 1;116 if x<=m then exit(ask(i*2,l,m,x))117 else exit(ask(i*2+1,m+1,r,x));118 end;119 end;120 121 begin122 readln(n,m);123 for i:=1 to n do124 begin125 read(a[i]);126 b[i]:=a[i];127 end;128 sort2(1,n);129 if b[1]<>0 then130 begin131 inc(t);132 d[1]:=0;133 end;134 inc(t);135 d[t]:=b[1];136 for i:=2 to n do137 begin138 if b[i]=b[i-1] then continue;139 if b[i]-b[i-1]>1 then140 begin141 inc(t);142 d[t]:=b[i-1]+1;143 end;144 inc(t);145 d[t]:=b[i];146 end;147 inc(t);148 d[t]:=b[n]+1;149 k:=1;150 for i:=1 to n do151 begin152 loc[i]:=find(a[i]);153 v[loc[i]]:=true;154 while v[k] do inc(k);155 sg[i]:=k;156 end;157 fillchar(last,sizeof(last),255);158 fillchar(next,sizeof(next),255);159 for i:=n downto 1 do160 begin161 next[i]:=last[loc[i]];162 last[loc[i]]:=i;163 end;164 165 build(1,1,n);166 for i:=1 to m do167 begin168 readln(p[i],q[i]);169 c[i]:=i;170 end;171 172 sort1(1,m);173 j:=1;174 for i:=1 to n do175 begin176 while p[j]=i do177 begin178 ans[c[j]]:=ask(1,1,n,q[j]);179 inc(j);180 end;181 if next[i]=-1 then next[i]:=n+1;182 work(1,1,n,i+1,next[i]-1,loc[i]);183 end;184 for i:=1 to m do185 writeln(d[ans[i]]);186 end.