bzoj3166

首先不难想到穷举次大数
然后我们只要找到满足这个数是次大数的最大区间即可
显然答案只可能是这两种[LL[i]+1,R[i]-1]和[L[i]+1,RR[i]-1]
L[i]表示这个数ai左侧第一个比它大的数的位置，
LL[i]表示这个数ai左侧第二个比它的的数的位置
R[i],RR[i]同理
然后假如我们能快速求出这两个区间，那剩下来我们就可以交给可持久化trie解决
下面的问题是如何快速求这两个区间
首先L[i],R[i]比较简单，直接维护一个单调降的队列即可
问题就是LL[i],RR[i]，这里就只讲LL[i]了
关注到LL[i]一定在L[i]左侧，从L[i]左侧第一个数考虑，如果它比a[i]大，那它就是左边大于a[i]的第二个数
如果小于，那么L[L[i]-1]+1~L[i]-1一定也不会比a[i]大，我们可以直接跳跃到L[L[i]-1]，以此类推
这样处理完所有的LL[i]，类似于最大子矩形的做法，均摊是O(n)
由此可以解决

 var son:array[-..,..] of longint;

     h,ll,l,r,rr,q,a:array[-..] of longint;

     n,t,x,i,s,ans:longint;

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

   begin

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

   end;

 function add(x,p:longint):longint;

   var i,q,y:longint;

   begin

     inc(t);

     add:=t;

     q:=t;

     for i:= downto  do

     begin

       y:=x and ( shl i);

       if y> then y:=;

       inc(t);

       son[q,y]:=t;

       son[q,-y]:=son[p,-y];

       p:=son[p,y];

       q:=t;

     end;

   end;

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

   var i,q,y:longint;

   begin

     ask:=;

     for i:= downto  do

     begin

       y:=x and ( shl i);

       if y> then y:=;

       if (son[r,-y]=-) or (son[r,-y]=son[l,-y]) then

       begin

         r:=son[r,y];

         l:=son[l,y];

       end

       else begin

         ask:=ask+ shl i;

         r:=son[r,-y];

         l:=son[l,-y];

       end;

     end;

   end;

 function sl(k:longint):longint;

   begin

     if (a[i]<a[k]) or (k=) then exit(k)

     else exit(sl(l[k]));

   end;

 function sr(k:longint):longint;

   begin

     if (a[i]<a[k]) or (k=n+) then exit(k)

     else exit(sr(r[k]));

   end;

 begin

   readln(n);

   fillchar(son,sizeof(son),);

   h[]:=;

   t:=;

   x:=;

   for i:= downto  do

   begin

     inc(t);

     son[x,]:=t;

   end;

   for i:= to n do

   begin

     read(a[i]);

     h[i]:=add(a[i],h[i-]);

   end;

   a[n+]:=;

   a[]:=;

   q[]:=;

   s:=;

   for i:= to n do

   begin

     while (s>) and (a[i]>a[q[s]]) do dec(s);

     l[i]:=q[s];

     inc(s);

     q[s]:=i;

   end;

   q[]:=n+;

   q[]:=n;

   s:=;

   r[n]:=n+;

   for i:=n- downto  do

   begin

     while (s>) and (a[i]>a[q[s]]) do dec(s);

     r[i]:=q[s];

     inc(s);

     q[s]:=i;

   end;

   ll[]:=;

   for i:= to n do

     if l[i]> then ll[i]:=sl(l[i]-)

     else ll[i]:=;

   rr[n]:=n+;

   i:=;

   for i:=n- downto  do

     if r[i]<=n then rr[i]:=sr(r[i]+)

     else rr[i]:=n+;

   ans:=;

   for i:= to n do

   begin

     if (l[i]=) and (r[i]=n+) then continue;

     if (l[i]=) then

       ans:=max(ans,ask(h[],h[rr[i]-],a[i]))

     else if r[i]=n+ then

       ans:=max(ans,ask(h[ll[i]],h[n],a[i]))

     else begin

       ans:=max(ans,ask(h[ll[i]],h[r[i]-],a[i]));

       ans:=max(ans,ask(h[l[i]],h[rr[i]-],a[i]));

     end;

   end;

   writeln(ans);

 end.

巴特西

bzoj3166

最新文章

热门文章