THUSC Day -1 训练日记

Codeforces 200A

有很多种思路……
我第一想法是先把候选坐标序列求出来，然后找到第一个未被占领的坐标，这样可以转化成LCP，用树状数组+二分做。
但因为边界原因这个方法必须把地图大小扩展到10000*10000，直接就挂了
然后考虑坐标旋转(x,y)=>(x+y,x-y)，这样首先我们可以发现，可以先二分出最小的绝对值和。这个坐标转化后是矩形用个二维树状数组维 护一下就好了。二分出这个答案S后，可以发现，距离(x,y)曼哈顿距离小于等于S的点坐标转化后图形肯定是一个矩形框，中间没有点（否则就有小于S的解 了），然后考虑坐标转化后的矩形的4个象限，每个象限内又是具有二分性质的（画个图就知道了），因此可以枚举每个象限，再二分一次求出最终答案。这样虽然 理论可行，但代码会很恶心，复杂度也不太靠谱O(Klg^3N)的…… （刚才翻了AC的人的代码，发现真有人这么做的orz……）
最后想到了暴力……… 暴力可以维护每一行可用的块，然后直接搞，可以O(NK)，这样K=10^5,N=2000,感觉压力大，但实际可以过……
于是就瞎狗眼了

code

var
n,m:longint;
prev,next:array[0..2010,0..2010] of longint;
 
procedure upd(var ax,ay,dx,dy:longint; _ax,_ay,_dx,_dy:longint);
var f:boolean;
begin if (_dx<=0)or(_dx>n)or(_dy<=0)or(_dy>m) then exit;
      f:=false;
      if _ax+_ay<>ax+ay then if _ax+_ay<ax+ay then f:=true else exit;
      if not f then if _dx<>dx then if _dx<dx then f:=true else exit;
      if not f then if _dy>=dy then exit;
      ax:=_ax; ay:=_ay; dx:=_dx; dy:=_dy;
end;
 
procedure lemon();
var man,i,j,k,x,y,ax,ay,dx,dy:longint;
begin readln(n,m,man);
      for i:=1 to n do
            for j:=0 to m+1 do
            begin prev[i,j]:=j;
                  next[i,j]:=j;
            end;
      for i:=1 to man do
      begin readln(x,y); ax:=10000; ay:=10000; dx:=0; dy:=0;
            for k:=x downto 1 do
            begin if x-k>ax+ay then break;
                  upd(ax,ay,dx,dy,x-k,y-prev[k,y],k,prev[k,y]);
                  upd(ax,ay,dx,dy,x-k,next[k,y]-y,k,next[k,y]);
            end;
            for k:=x to n do
            begin if k-x>ax+ay then break;
                  upd(ax,ay,dx,dy,k-x,y-prev[k,y],k,prev[k,y]);
                  upd(ax,ay,dx,dy,k-x,next[k,y]-y,k,next[k,y]);
            end;
            writeln(dx,' ',dy);
            for k:=1 to dy do if next[dx,k]=dy then next[dx,k]:=next[dx,dy+1];
            for k:=m downto dy do if prev[dx,k]=dy then prev[dx,k]:=prev[dx,dy-1];
      end;
end;
 
begin
lemon();
end.

国家集训队互测题 陈丽洁 middle

给定一个序列，求左端点在[a,b]，右端点在[c,d]的子序列的最大中位数。
大概是二分答案，然后变成+1,-1序列，转化为前后缀最大和。
然后这个转化序列不太好搞，于是我们发现可以用函数式数据结构把所有的n棵线段树都建起来就行了。
二分的细节很多

code

type
      pointer=^node;
      node=record
                  left,right,mid,len,sum,lmax,rmax:longint;
                  lc,rc:pointer;
            end;
 
function build(bg,ed:longint):pointer;
begin new(build);
      with build^ do
      begin left:=bg; right:=ed;
            mid:=(left+right)>>1;
            len:=right-left+1; 
            sum:=len; lmax:=len; rmax:=len;
            lc:=nil; rc:=nil; 
            if left=right then exit;
            lc:=build(bg,mid); rc:=build(mid+1,ed);
      end;
end;
 
function max2(x,y:longint):longint;
begin if x>y then exit(x) else exit(y); end;
 
function serere(root:pointer; where,dt:longint):pointer;
begin new(serere); serere^:=root^;
      with serere^ do
      begin if left=right then 
            begin sum:=dt; if dt>0 then lmax:=dt else lmax:=0;
                  rmax:=lmax; exit;
            end;
            if where<=mid then lc:=serere(lc,where,dt) else rc:=serere(rc,where,dt);
            lmax:=max2(lc^.lmax,lc^.sum+rc^.lmax);
            rmax:=max2(rc^.rmax,rc^.sum+lc^.rmax);
            sum:=lc^.sum+rc^.sum;
      end;
end;
 
type
      atype=record dt,where:longint; end;
 
var
e:array[0..20010] of atype;
 
procedure sort(l,r:longint);
var i,j:longint;
    x,y:atype;
begin i:=l;
      j:=r;
      x:=e[l+random(r-l+1)];
      repeat
            while e[i].dt<x.dt do inc(i);
            while x.dt<e[j].dt do dec(j);
            if not(i>j) then
            begin y:=e[i]; e[i]:=e[j]; e[j]:=y;
                  inc(i); j:=j-1;
            end;
      until i>j;
      if l<j then sort(l,j);
      if i<r then sort(i,r);
end;
 
type
      restype=record sum,lmax,rmax:longint; end;
 
function mp(x,y,z:longint):restype;
begin mp.sum:=x; mp.lmax:=y; mp.rmax:=z; end;
 
function query(root:pointer; bg,ed:longint):restype;
var r1,r2:restype;
begin with root^ do
      begin if (bg<=left)and(right<=ed) then exit(mp(sum,lmax,rmax));
            if ed<=mid then exit(query(lc,bg,ed));
            if mid<bg then exit(query(rc,bg,ed));
            r1:=query(lc,bg,ed); r2:=query(rc,bg,ed);
            query.sum:=r1.sum+r2.sum;
            query.lmax:=max2(r1.lmax,r1.sum+r2.lmax);
            query.rmax:=max2(r2.rmax,r2.sum+r1.rmax);
      end;
end;
 
var
q:array[1..4] of longint;
root:array[0..20010] of pointer;
d:array[0..20010] of longint;
 
procedure lemon();
var n,i,j,cur,last,k,left,right,mid,all,temp,_Q,lastans,ans:longint;
begin readln(n); 
      for i:=1 to n do begin read(e[i].dt); e[i].where:=i; end;
      sort(1,n);
      root[0]:=build(1,n);
      all:=0; last:=1; cur:=1;
      while cur<=n do
      begin inc(all); root[all]:=root[all-1]; d[all]:=e[cur].dt;
            //for j:=last to cur-1 do root[all]:=serere(root[all],e[j].where,-1);
            last:=cur;
            while (cur<=n)and(e[cur].dt=e[last].dt) do 
            begin root[all]:=serere(root[all],e[cur].where,-1);
                  inc(cur);
            end;
      end;
      readln(_Q); lastans:=0;
      for i:=1 to _Q do
      begin for j:=1 to 4 do begin read(q[j]); q[j]:=int64(q[j]+lastans) mod n+1; end;
            for j:=1 to 3 do
                  for k:=j+1 to 4 do
                        if q[j]>q[k] then
                        begin temp:=q[j]; q[j]:=q[k]; q[k]:=temp; end;
            left:=1; right:=all; ans:=0;
            while left<=right do
            begin mid:=(left+right)>>1;
                  if query(root[mid],q[1],q[2]-1).rmax+query(root[mid],q[2],q[3]).sum+query(root[mid],q[3]+1,q[4]).lmax>=0 then
                  begin ans:=mid;
                        left:=mid+1;
                   end
                  else  right:=mid-1;
            end;
            writeln(d[ans+1]); lastans:=d[ans+1];
      end;
end;
 
begin
lemon();
end.