LEM4 - WHITE BLACK

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const fi='';
      maxn=10010;
var n,m,i,x,y,z:longint;
    a,g,h,f:array[1..maxn shl 2] of longint;

procedure put(x,val:longint);
begin
     f[x]:=val; g[x]:=val; h[x]:=val;
end;

procedure add(node,l,r,x,y,z:longint);
var mid:longint;
begin
     if (l=x) and (r=y) then
     begin
          a[node]:=z;
          if z=1 then put(node,r-l+1)
          else put(node,0);
     end
     else
     begin
          mid:=(l+r) shr 1;
          if a[node]<>0 then
          begin
               a[node shl 1]:=a[node];
               a[node shl 1+1]:=a[node];
               put(node shl 1,(mid-l+1)*(2-a[node]));
               put(node shl 1+1,(r-mid)*(2-a[node]));
               a[node]:=0;
          end;
          if x<=mid then add(node shl 1,l,mid,x,min(y,mid),z);
          if mid<y then add(node shl 1+1,mid+1,r,max(x,mid+1),y,z);
          if g[node shl 1]=mid-l+1 then g[node]:=mid-l+1+g[node shl 1+1]
          else g[node]:=g[node shl 1];
          if h[node shl 1+1]=r-mid then h[node]:=h[node shl 1]+r-mid
          else h[node]:=h[node shl 1+1];
          f[node]:=max(f[node shl 1],f[node shl 1+1]);
          f[node]:=max(f[node],h[node shl 1]+g[node shl 1+1]);
     end;
end;

begin
     assign(input,fi); reset(input);
     read(n,m);
     add(1,1,n,1,n,1);
     for i:=1 to m do
     begin
          read(z);
          if z=3 then writeln(f[1])
          else
          begin
               read(x,y);
               add(1,1,n,x,y,z);
          end;
     end;
     close(input);
end.

Download