LITES - Bật đèn

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100000;
  snode=524288;
var
  bat,tat,val:array[1..snode] of longint;
  n,q:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure update(u,v: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
        if val[i]=0 then swap(bat[i],tat[i])
        else val[i]:=0;
        val[i<<1]:=1-val[i<<1];
        val[i<<1+1]:=1-val[i<<1+1];
        exit;
      end;
    mid:=(l+r)>>1;
    if val[i<<1]=1 then
      begin
        val[i<<1]:=0;
        swap(bat[i<<1],tat[i<<1]);
        val[i<<2+0]:=1-val[i<<2+0];
        val[i<<2+1]:=1-val[i<<2+1];
      end;
    if val[i<<1+1]=1 then
      begin
        val[i<<1+1]:=0;
        swap(bat[i<<1+1],tat[i<<1+1]);
        val[i<<2+2]:=1-val[i<<2+2];
        val[i<<2+3]:=1-val[i<<2+3];
      end;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
    bat[i]:=bat[i<<1]+bat[i<<1+1];
    tat[i]:=tat[i<<1]+tat[i<<1+1];
  end;
begin
  visit(1,1,n);
end;
function get(u,v:longint):longint;
var
  kq: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
        if val[i]=1 then
          begin
            val[i]:=0;
            swap(bat[i],tat[i]);
            val[i<<1]:=1-val[i<<1];
            val[i<<1+1]:=1-val[i<<1+1];
          end;
        inc(kq,bat[i]);
        exit;
      end;
    mid:=(l+r)>>1;
    if val[i]=1 then
      begin
        val[i]:=0;
        swap(bat[i],tat[i]);
        val[i<<1+0]:=1-val[i<<1+0];
        val[i<<1+1]:=1-val[i<<1+1];
      end;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  kq:=0;
  visit(1,1,n);
  get:=kq;
end;
procedure build(i,l,r:longint);
var
  mid:longint;
begin
  if l=r then
    begin
      bat[i]:=0;
      tat[i]:=1;
      exit;
    end;
  mid:=(l+r)>>1;
  build(i<<1,l,mid);
  build(i<<1+1,mid+1,r);
  bat[i]:=bat[i<<1]+bat[i<<1+1];
  tat[i]:=tat[i<<1]+tat[i<<1+1];
end;
procedure solve;
var
  u,v,yc:longint;
begin
  for q:=1 to q do
    begin
      read(f1,yc);
      if yc=0 then
        begin
          read(f1,u,v);
          update(u,v);
        end
      else //if yc=1 then
        begin
          read(f1,u,v);
          writeln(f2,get(u,v));
        end;
    end;
end;
begin
  openF;
  read(f1,n,q);
  build(1,1,n);
  solve;
  closeF;
end.

Download