3212: Pku3468 A Simple Problem with Integers
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1053 Solved: 468[][][]Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
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
The sums may exceed the range of 32-bit integers.
Source
题解：其实就是个英文版的线段树模板题，连乘法覆盖啥的都没有，也就是说所有的修改操作压根就没有顺序之分，可以爱怎么瞎搞怎么瞎搞= =
PS：话说我的线段树居然全方位怒踩树状数组是什麽节奏啊啊啊QAQ（上面的是树状数组，下面的是线段树）
树状数组：
1 /************************************************************** 2 Problem: 3212 3 User: HansBug 4 Language: Pascal 5 Result: Accepted 6 Time:268 ms 7 Memory:15852 kb 8 ****************************************************************/ 9 10 var11 b,c:array[0..1000005] of int64;12 i,j,k,l,m,n:longint;a1:int64;ch:char;13 procedure addb(x:longint;y:int64);14 begin15 while x>0 do16 begin17 inc(b[x],y);18 dec(x,x and (-x));19 end;20 end;21 procedure addc(x:longint;y:int64);22 var z:int64;23 begin24 z:=x;if x=0 then exit;25 while x<=n do26 begin27 inc(c[x],z*y);28 inc(x,x and (-x));29 end;30 end;31 function sumb(x:longint):int64;32 begin33 sumb:=0;if x=0 then exit;34 while x<=n do35 begin36 inc(sumb,b[x]);37 inc(x,x and (-x));38 end;39 end;40 function sumc(x:longint):int64;41 begin42 sumc:=0;43 while x>0 do44 begin45 inc(sumc,c[x]);46 dec(x,x and (-x));47 end;48 end;49 function summ(x:longint):int64;50 begin51 exit(sumb(x)*int64(x)+sumc(x-1));52 end;53 procedure add(x,y:longint;z:int64);54 begin55 addb(y,z);addc(y,z);56 addb(x-1,-z);addc(x-1,-z);57 end;58 function sum(x,y:longint):int64;59 begin60 exit(summ(y)-summ(x-1));61 end;62 begin63 readln(n,m);64 fillchar(b,sizeof(b),0);65 fillchar(c,sizeof(c),0);66 for i:=1 to n do67 begin68 read(a1);69 add(i,i,a1);70 end;readln;71 for i:=1 to m do72 begin73 read(ch);74 case upcase(ch) of75 'Q':begin76 readln(j,k);77 writeln(sum(j,k));78 end;79 'C':begin80 readln(j,k,a1);81 add(j,k,a1);82 end;83 end;84 end;85 end.
线段树：
1 /************************************************************** 2 Problem: 3212 3 User: HansBug 4 Language: Pascal 5 Result: Accepted 6 Time:84 ms 7 Memory:15852 kb 8 ****************************************************************/ 9 10 var11 i,j,k,l,m,n:longint;a1:int64;ch:char;12 a,b:array[0..1000005] of int64;13 function min(x,y:longint):longint;14 begin15 if xy then max:=x else max:=y;20 end;21 procedure built(z,x,y:longint);22 begin23 if x=y then24 read(a[z])25 else begin26 built(z*2,x,(x+y) div 2);27 built(z*2+1,(x+y) div 2+1,y);28 a[z]:=a[z*2]+a[z*2+1];29 end;30 b[z]:=0;31 end;32 procedure add(z,x,y,l,r:longint;t:int64);33 begin34 if l>r then exit;35 if (x=l) and (y=r) then36 begin37 inc(b[z],t);38 exit;39 end;40 inc(a[z],t*int64(r-l+1));41 add(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);42 add(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);43 end;44 function sum(z,x,y,l,r:longint;t:int64):int64;45 var a1,a2:int64;46 begin47 if l>r then exit(0);48 inc(t,b[z]);49 if (x=l) and (y=r) then exit(a[z]+t*int64(y-x+1));50 a1:=sum(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);51 a2:=sum(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);52 exit(a1+a2);53 end;54 begin55 readln(n,m);built(1,1,n);readln;56 for i:=1 to m do57 begin58 read(ch);59 case upcase(ch) of60 'Q':begin61 readln(j,k);62 writeln(sum(1,1,n,j,k,0));63 end;64 'C':begin65 readln(j,k,a1);66 add(1,1,n,j,k,a1);67 end;68 end;69 end;70 end.