LITES - Bật đèn

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program LITES2;
Const
  input  = '';
  output = '';
  maxn = 100000;
Type
  rec = record
    val: integer;
    swt,pre: boolean;
  end;
Var
  fi,fo: text;
  n,m,u,v: integer;
  a: array[1..8 * maxn] of rec;

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

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

Procedure update(i,low,high: integer);
Var
  mid,left,right: integer;
Begin
  If (v < low) or (high < u) then exit;
  If (u <= low) and (high <= v) then
    Begin
      a[i].swt:= not a[i].swt;
      exit;
    End;

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

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

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

  a[i].val:= left + right;
End;

Function calc(i,low,high: integer): integer;
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit(0);
  If (u <= low) and (high <= v) then
    If not (a[i].swt xor a[i].pre) then exit(a[i].val)
                                   else exit(high - low + 1 - a[i].val);

  mid:= (low + high) div 2;
  a[2 * i].pre:= a[i].swt xor a[i].pre;
  a[2 * i + 1].pre:= a[2 * i].pre;
  calc:= calc(2 * i,low,mid) + calc(2 * i + 1,mid + 1,high);
End;

Procedure swap(var x,y: integer);
Var
  t: integer;
Begin
  t:= x;
  x:= y;
  y:= t;
End;

Procedure solve;
Var
  i,q: integer;
Begin
  For i:= 1 to 8 * maxn do
    Begin
      a[i].val:= 0;
      a[i].swt:= false;
    End;
  a[1].pre:= false;

  Readln(fi, n, m);
  For i:= 1 to m do
    Begin
      Readln(fi, q, u, v);
      If u > v then swap(u,v);
      If q = 0 then update(1,1,n) else writeln(fo, calc(1,1,n));
    End;
End;

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

Begin
  openfile;
  solve;
  closefile;
End.

Download