bzoj3339 bzoj3585

两题本质是一样，只不过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，
显然修改操作我们可以用线段树来维护，这样就解决了这个问题

 const inf=;

 var loc,ans,next,last,sg,p,q,c,a,b:array[..] of longint;

     tree:array[..] of longint;

     d:array[..] of longint;

     v:array[..] of boolean;

     i,n,m,j,t,k:longint;

 procedure swap(var a,b:longint);

   var c:longint;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 function min(a,b:longint):longint;

   begin

     if a>b then exit(b) else exit(a);

   end;

 function find(x:longint):longint;

   var l,r,m:longint;

   begin

     l:=;

     r:=t;

     while l<=r do

     begin

       m:=(l+r) shr ;

       if d[m]=x then exit(m);

       if d[m]>x then r:=m- else l:=m+;

     end;

   end;

 procedure sort1(l,r:longint);

   var i,j,x,y: longint;

   begin

     i:=l;

     j:=r;

     x:=p[(l+r) div ];

     repeat

       while p[i]<x do inc(i);

       while x<p[j] do dec(j);

       if not(i>j) then

       begin

         swap(p[i],p[j]);

         swap(q[i],q[j]);

         swap(c[i],c[j]);

         inc(i);

         j:=j-;

       end;

     until i>j;

     if l<j then sort1(l,j);

     if i<r then sort1(i,r);

   end;

 procedure sort2(l,r:longint);

   var i,j,x,y: longint;

   begin

     i:=l;

     j:=r;

     x:=b[(l+r) div ];

     repeat

       while b[i]<x do inc(i);

       while x<b[j] do dec(j);

       if not(i>j) then

       begin

         swap(b[i],b[j]);

         inc(i);

         j:=j-;

       end;

     until i>j;

     if l<j then sort2(l,j);

     if i<r then sort2(i,r);

   end;

 procedure build(i,l,r:longint);

   var m:longint;

   begin

     if l=r then

       tree[i]:=sg[l]

     else begin

       tree[i]:=inf;

       m:=(l+r) shr ;

       build(i*,l,m);

       build(i*+,m+,r);

     end;

   end;

 procedure push(i:longint);

   begin

     tree[i*]:=min(tree[i*],tree[i]);

     tree[i*+]:=min(tree[i*+],tree[i]);

     tree[i]:=inf;

   end;

 procedure work(i,l,r,x,y,z:longint);

   var m:longint;

   begin

     if (x<=l) and (y>=r) then

       tree[i]:=min(tree[i],z)

     else begin

       if tree[i]<>inf then push(i);

       m:=(l+r) shr ;

       if x<=m then work(i*,l,m,x,y,z);

       if y>m then work(i*+,m+,r,x,y,z);

     end;

   end;

 function ask(i,l,r,x:longint):longint;

   var m:longint;

   begin

     if l=r then exit(tree[i])

     else begin

       if tree[i]<>inf then push(i);

       m:=(l+r) shr ;

       if x<=m then exit(ask(i*,l,m,x))

       else exit(ask(i*+,m+,r,x));

     end;

   end;

 begin

   readln(n,m);

   for i:= to n do

   begin

     read(a[i]);

     b[i]:=a[i];

   end;

   sort2(,n);

   if b[]<> then

   begin

     inc(t);

     d[]:=;

   end;

   inc(t);

   d[t]:=b[];

   for i:= to n do

   begin

     if b[i]=b[i-] then continue;

     if b[i]-b[i-]> then

     begin

       inc(t);

       d[t]:=b[i-]+;

     end;

     inc(t);

     d[t]:=b[i];

   end;

   inc(t);

   d[t]:=b[n]+;

   k:=;

   for i:= to n do

   begin

     loc[i]:=find(a[i]);

     v[loc[i]]:=true;

     while v[k] do inc(k);

     sg[i]:=k;

   end;

   fillchar(last,sizeof(last),);

   fillchar(next,sizeof(next),);

   for i:=n downto  do

   begin

     next[i]:=last[loc[i]];

     last[loc[i]]:=i;

   end;

   build(,,n);

   for i:= to m do

   begin

     readln(p[i],q[i]);

     c[i]:=i;

   end;

   sort1(,m);

   j:=;

   for i:= to n do

   begin

     while p[j]=i do

     begin

       ans[c[j]]:=ask(,,n,q[j]);

       inc(j);

     end;

     if next[i]=- then next[i]:=n+;

     work(,,n,i+,next[i]-,loc[i]);

   end;

   for i:= to m do

     writeln(d[ans[i]]);

 end.

巴特西

bzoj3339 bzoj3585

最新文章

热门文章