64

1858 ワード

         (    )
        (500000)^(1/3)=80    o((n/k)^2)+n log n+n*k)          4.8s 
      (             )
             
var i,j,k,l,m,n,q,w,x,y:longint;
    a,b,next,c,t:array[0..500000] of longint;
    f:array[0..6300,0..6300] of longint;
function jh(p,o:longint):boolean;
begin
   if a[p]=a[o] then exit(po then exit(o);exit(p);end;
procedure sort(l,r: longint);
      var i,j,x,y: longint;
      begin
         i:=l; j:=r; x:=b[(l+r)div 2];
         repeat
           while jh(b[i],x) do inc(i);
           while jh(x,b[j]) do dec(j);
           if i<=j then
             begin
                y:=b[i]; b[i]:=b[j]; b[j]:=y;
                inc(i); j:=j-1;
             end;
         until i>=j;
         if l0) then c[i]:=next[i]-i;
    for i:=1 to n do t[i]:=(i-1) div k+1;
    fillchar(f,sizeof(f),$7f);
    for i:=1 to n do if next[i]<>0 then
        f[t[i],t[next[i]]]:=min(c[i],f[t[i],t[next[i]]]);
    for i:=1 to l do for j:=i+1 to l do begin
        f[i,j]:=min(f[i,j-1],f[i,j]); f[i,j]:=min(f[j,j],f[i,j]);end;
    for i:=1 to m  do begin
        readln(x,y);
        x:=x xor q; y:=y xor q;
        if t[y]-t[x]<2 then begin q:=maxlongint;
         for j:=x to y do if (0n then q:=-1;  writeln(q);
        end
        else begin
          q:=f[t[x]+1,t[y]-1];
           for j:=x to t[x]*k do
               if(0n then q:=-1; writeln(q);
        end;
    end;
end.