POJ 3468(成段更新）
2012-11-15 09:11:15

Time Limit: 5000MS   Memory Limit: 131072K
Total Submissions: 38010   Accepted: 11017
Case Time Limit: 2000MS
Description

Input www.2cto.com

"C a b c" 表示将 Aa, Aa+1, ... , Ab.加上c. -10000 ≤ c ≤ 10000.
"Q a b" 输出区间[a,b]的和。
Output

Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
Hint
longint会爆的。
Source
POJ Monthly--2007.11.25, Yang Yi

[delphi]
Program poj3468;
const
maxn=100000;
maxq=100000;
var
n,m,i,j,k:longint;
lazy,t:array[1..maxn*8] of int64;
c:char;
Procedure pushup(root:longint);
begin
t[root]:=t[root*2]+t[root*2+1];
end;
Procedure build(l,r,root:longint);
var
m:longint;
begin
if (l=r) then
begin
exit;
end;
m:=(l+r) shr 1;
build(l,m,root*2);
build(m+1,r,root*2+1);
pushup(root);
end;
Procedure Pushdown(l,r,root:longint);
var
m:longint;
begin
m:=(l+r) shr 1;
if (lazy[root]=0) then exit;
inc(lazy[root shl 1],lazy[root]);
inc(lazy[root shl 1+1],lazy[root]);
inc(t[root shl 1],lazy[root]*(m-l+1));
inc(t[root shl 1+1],lazy[root]*(r-(m+1)+1));

lazy[root]:=0;
end;
Procedure update(l,r,nowl,nowr,root,cost:longint);
var
m:longint;
begin
if (l<=nowl) and (nowr<=r) then
begin
inc(lazy[root],cost);
inc(t[root],(nowr-nowl+1)*cost);
exit;
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
if (l<=m) then update(l,r,nowl,m,root*2,cost);
if (m+1<=r) then update(l,r,m+1,nowr,root*2+1,cost);
pushup(root);
end;
function query(l,r,nowl,nowr,root:longint):int64;
var
m:longint;
res:int64;
begin
if (l<=nowl) and (nowr<=r) then
begin
exit(t[root]);
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
res:=0;
if (l<=m) then res:=res+query(l,r,nowl,m,root*2);
if (m+1<=r) then res:=res+query(l,r,m+1,nowr,root*2+1);
exit(res);
end;

begin
fillchar(lazy,sizeof(lazy),0);
build(1,n,1);
while (m>0) do
begin
if c='Q' then
begin
writeln(query(i,j,1,n,1));
end
else
begin
update(i,j,1,n,1,k);
end;

dec(m);
end;
end.