如题,实现一个程序,输入N个数,进行如下维护:
1.1 x y 求[x,y]区间的和
2.2 x y 求[x,y]区间的平方和
3.3 x y z 将[x,y]区间全部加上z
4.4 x y 求[x,y]区间内两两数相乘的积之和(其实4是1、2的简单组合)
如下:
1 var
2 i,j,k,l,m,n:longint;
3 t:int64;
4 a,b,c:array[0..100000] of int64;
5 type
6 rec=record
7 aa,bb:int64;
8 end;
9
10 function max(x,y:longint):longint;
11 begin
12 if x>y then max:=x else max:=y;
13 end;
14 function min(x,y:longint):longint;
15 begin
16 if x<y then min:=x else min:=y;
17 end;
18 procedure built(z,x,y:longint);
19 begin
20 if x=y then
21 begin
22 read(a[z]);
23 b[z]:=a[z]*a[z];
24 end
25 else
26 begin
27 built(z*2,x,(x+y) div 2);
28 built(z*2+1,(x+y) div 2+1,y);
29 a[z]:=a[z*2]+a[z*2+1];
30 b[z]:=b[z*2]+b[z*2+1];
31 end;
32 c[z]:=0;
33 end;
34 procedure ext(z,x,y:longint);
35 begin
36 if c[z]=0 then exit;
37 b[z]:=b[z]+2*c[z]*a[z]+(y-x+1)*c[z]*c[z];
38 a[z]:=a[z]+(y-x+1)*c[z];
39 if x<>y then
40 begin
41 c[z*2]:=c[z*2]+c[z];
42 c[z*2+1]:=c[z*2+1]+c[z];
43 end;
44 c[z]:=0;
45 end;
46 function suma(z,x,y,l,r:longint):int64;
47 begin
48 if l>r then exit(0);
49 ext(z,x,y);
50 if (x=l) and (y=r) then exit(a[z]);
51 exit(suma(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2))+suma(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r));
52 end;
53 function sumb(z,x,y,l,r:longint):int64;
54 begin
55 if l>r then exit(0);
56 ext(z,x,y);
57 if (x=l) and (y=r) then exit(b[z]);
58 exit(sumb(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2))+sumb(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r));
59 end;
60 function add(z,x,y,l,r:longint;t:int64):rec;
61 var tt,tt1,tt2:rec;
62 begin
63 tt.aa:=0;tt.bb:=0;
64 if l>r then exit(tt);
65 if (x=l) and (y=r) then
66 begin
67 tt.aa:=t*(r-l+1);
68 tt.bb:=2*t*(a[z]+c[z]*(r-l+1))+t*t*(r-l+1);
69 c[z]:=c[z]+t;
70 exit(tt);
71 end;
72 ext(z,x,y);
73 tt1:=add(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
74 tt2:=add(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
75 tt.aa:=tt1.aa+tt2.aa;
76 tt.bb:=tt1.bb+tt2.bb;
77 a[z]:=a[z]+tt.aa;
78 b[z]:=b[z]+tt.bb;
79 exit(tt);
80 end;
81 begin
82 readln(n);
83 built(1,1,n);
84 while true do
85 begin
86 read(j,k,l);
87 case j of
88 1:begin
89 writeln(suma(1,1,n,k,l));
90 end;
91 2:begin
92 writeln(sumb(1,1,n,k,l));
93 end;
94 3:begin
95 read(t);
96 add(1,1,n,k,l,t);
97 end;
98 4:begin
99 t:=suma(1,1,n,k,l);
100 writeln((t*t-sumb(1,1,n,k,l)) div 2);
101 end;
102 end;
103 readln;
104 end;
105 end.
106