TYVJ1661 (Pascal)

tyvj1661.pas

type
  seg=record
      left,right:longint;
      add,sum:int64;
    end;

var
  a:array [0..500000] of seg;
  n,k,l,r,i:longint;
  order:char;
  num:int64;

procedure tr_create(p,l,r:longint);
var
  m:longint;

begin
  a[p].left:=l;
  a[p].right:=r;
  a[p].add:=0;
  if l=r then begin read(a[p].sum); exit; end;
  m:=(l+r) shr 1;
  tr_create(p shl 1,l,m);
  tr_create(p shl 1+1,m+1,r);
  a[p].sum:=a[p shl 1].sum+a[p shl 1+1].sum;
end;

procedure tr_update(p:longint);
begin
  if a[p].add<>0 then
    begin
      inc(a[p shl 1].add,a[p].add);
      inc(a[p shl 1+1].add,a[p].add);
      inc(a[p].sum,a[p].add*(a[p].right-a[p].left+1));
      a[p].add:=0;
    end;
end;

procedure tr_add(p,l,r:longint; num:int64);
begin
  tr_update(p);
  if (l<=a[p].left) and (r>=a[p].right) then
    begin
      inc(a[p].add,num);
      exit;
    end;
  if l<=a[p shl 1].right then tr_add(p shl 1,l,r,num);
  if r>=a[p shl 1+1].left then tr_add(p shl 1+1,l,r,num);
//  tr_update(p shl 1);
//  tr_update(p shl 1+1);
  a[p].sum:=a[p shl 1].sum+a[p shl 1+1].sum;
end;

function tr_query(p,l,r:longint):int64;
var
  tmp:int64;

begin
  tr_update(p);
  tmp:=0;
  if (l<=a[p].left) and (r>=a[p].right) then exit(a[p].sum);
  if l<=a[p shl 1].right then inc(tmp,tr_query(p shl 1,l,r));
  if r>=a[p shl 1+1].left then inc(tmp,tr_query(p shl 1+1,l,r));
//  tr_update(p shl 1);
//  tr_update(p shl 1+1);
  a[p].sum:=a[p shl 1].sum+a[p shl 1+1].sum;
  exit(tmp);
end;

begin
  readln(n,k);
  tr_create(1,1,n);
  readln;
  for i:=1 to k do
    begin
      read(order,l,r);
      if l=0 then l:=1;
      if order='C' then
        begin
          if r=0 then writeln(0) else writeln(tr_query(1,l,r));
          readln;
          continue;
        end;
      readln(num);
      if order='-' then num:=-num;
      tr_add(1,l,r,num);
    end;
end.