LITES - Bật đèn

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const maxn=100010;
      fi='';
var n,m,x,y,z,i,re:longint;
    a:array[1..maxn*5] of longint;
    b:array[1..maxn*5] of byte;

procedure add(node,l,r,x,y:longint);
var mid,t,u:longint;
begin
     if (l=x) and (r=y) then
     begin
          a[node]:=r-l+1-a[node];
          b[node]:=b[node] xor 1;
          exit;
     end;
     mid:=(l+r) shr 1;
     if x<=mid then add(node shl 1,l,mid,x,min(y,mid));
     if mid<y then add(node shl 1+1,mid+1,r,max(mid+1,x),y);
     a[node]:=a[node shl 1]+a[node shl 1+1];
     if b[node]=1 then a[node]:=r-l+1-a[node];
end;

procedure calc(node,l,r,x,y,z:longint;var re:longint);
var mid,t,u:longint;
begin
     if (l=x) and (r=y) then
     begin
          if z=0 then re:=a[node]
          else re:=r-l+1-a[node];
          exit;
     end;
     mid:=(l+r) shr 1; t:=0; u:=0;
     z:=z xor b[node];
     if x<=mid then calc(node shl 1,l,mid,x,min(y,mid),z,t);
     if mid<y then  calc(node shl 1+1,mid+1,r,max(mid+1,x),y,z,u);
     re:=t+u;
end;

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

Download