LEM4 - WHITE BLACK

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=10000;
  snode=262144;
var
  m,n:longint;
  f1,f2:text;
  left,right,maxkq,color:array[1..snode] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure update(u,v,k:longint);
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if (v<l) or (r<u) then exit;
    if (u<=l) and (r<=v) then
      begin
        color[i]:=k;
        if k=1 then
          begin
            left[i]:=r-l+1;
            right[i]:=r-l+1;
            maxkq[i]:=r-l+1;
          end
        else
          begin
            left[i]:=0;
            right[i]:=0;
            maxkq[i]:=0;
          end;
        exit;
      end;
    mid:=(l+r) shr 1;
    if color[i]=1 then
      begin
        color[i shl 1]:=1;
        left[i shl 1]:=mid-l+1; right[i shl 1]:=mid-l+1; maxkq[i shl 1]:=mid-l+1;
        color[i shl 1+1]:=1;
        left[i shl 1+1]:=r-mid; right[i shl 1+1]:=r-mid; maxkq[i shl 1+1]:=r-mid;
      end
    else if color[i]=2 then
      begin
        color[i shl 1]:=2;
        left[i shl 1]:=0; right[i shl 1]:=0; maxkq[i shl 1]:=0;
        color[i shl 1+1]:=2;
        left[i shl 1+1]:=0; right[i shl 1+1]:=0; maxkq[i shl 1+1]:=0;
      end;
    color[i]:=0;
    visit(i shl 1,l,mid);
    visit(i shl 1+1,mid+1,r);
    left[i]:=left[i shl 1];
    if color[i shl 1]=1 then left[i]:=left[i]+left[i shl 1+1];
    right[i]:=right[i shl 1+1];
    if color[i shl 1+1]=1 then right[i]:=right[i]+right[i shl 1];
    maxkq[i]:=max(max(maxkq[i shl 1],maxkq[i shl 1+1]),right[i shl 1]+left[i shl 1+1]);
    if (color[i shl 1]=color[i shl 1+1]) then color[i]:=color[i shl 1];
  end;
begin
  visit(1,1,n);
end;
procedure ans;
var
  i,k,u,v:longint;
begin
  for i:=1 to m do
    begin
      read(f1,k);
      if k=3 then writeln(f2,maxkq[1])
      else
        begin
          read(f1,u,v);
          update(u,v,k);
        end;
    end;
end;
begin
  openF;
  read(f1,n,m);
  color[1]:=1; left[1]:=n; right[1]:=n; maxkq[1]:=n;
  ans;
  closeF;
end.

Download