LEM4 - WHITE BLACK

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program LEM4_2;
Uses math;
Const
  input  = '';
  output = '';
  maxn = 10000;
  maxv = 20000;
Type
  rec = record
    left,right,val,sign: integer;
  end;
Var
  fi,fo: text;
  n,m,q,u,v: integer;
  a: array[1..8 * maxn] of rec;
  k: array[-1..1] of integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure setval(i,low,high: integer);
Var
  t: integer;
Begin
  t:= a[i].sign;
  a[i].val:= (high - low + 1) * t * k[t];
  a[i].left:= a[i].val;
  a[i].right:= a[i].val;
End;

Procedure update(i,low,high: integer);
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit;
  If (u <= low) and (high <= v) then
    Begin
      If q = 1 then a[i].sign:= 1 else a[i].sign:= -1;
      setval(i,low,high);
      exit;
    End;

  mid:= (low + high) div 2;
  If a[i].sign <> 0 then
    Begin
      a[2 * i].sign:= a[i].sign;
      a[2 * i + 1].sign:= a[i].sign;
      a[i].sign:= 0;

      setval(2 * i,low,mid);
      setval(2 * i + 1,mid + 1,high);
    End;

  update(2 * i,low,mid);
  update(2 * i + 1,mid + 1,high);

  a[i].left:= a[2 * i].left;
  If (a[2 * i].left = mid - low + 1)
    and (a[2 * i + 1].left > 0) then a[i].left:= a[2 * i].left + a[2 * i + 1].left;

  a[i].right:= a[2 * i + 1].right;
  If (a[2 * i + 1].right = high - mid)
    and (a[2 * i].right > 0) then a[i].right:= a[2 * i + 1].right + a[2 * i].right;

  a[i].val:= max(a[2 * i].val,a[2 * i + 1].val);
  If a[i].val < a[2 * i].right + a[2 * i + 1].left
    then a[i].val:= a[2 * i].right + a[2 * i + 1].left;
End;

Procedure solve;
Var
  i,t: integer;
Begin
  Read(fi, n, m);
  k[-1]:= maxv;
  k[1]:= 1;

  q:= 1;
  u:= 1;
  v:= n;
  update(1,1,n);

  For i:= 1 to m do
    Begin
      Read(fi, q);

      If q = 3 then
        Begin
          t:= a[1].val;
          If t < 0 then writeln(fo, 0) else writeln(fo, t);
        End
      else
        Begin
          Readln(fi, u, v);
          update(1,1,n);
        End;
    End;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  solve;
  closefile;
End.

Download