实现功能——1:区间开根;2:区间求和(此模板以BZOJ3038为例)
作为一个非常规的线段树操作,其tag也比较特殊呵呵哒
1 var
2 i,j,k,l,m,n:longint;
3 a,b:array[0..500000] of int64;
4 function max(x,y:longint):longint;inline;
5 begin
6 if x>y then max:=x else max:=y;
7 end;
8 function min(x,y:longint):longint;inline;
9 begin
10 if x<y then min:=x else min:=y;
11 end;
12 procedure built(z,x,y:longint);inline;
13 begin
14 if x=y then
15 begin
16 read(a[z]);
17 if a[z]<=1 then b[z]:=1 else b[z]:=0;
18 end
19 else
20 begin
21 built(z*2,x,(x+y) div 2);
22 built(z*2+1,(x+y) div 2+1,y);
23 a[z]:=a[z*2]+a[z*2+1];
24 if (b[z*2]=1) and (b[z*2+1]=1) then b[z]:=1 else b[z]:=0;
25 end;
26 end;
27 function op(z,x,y,l,r:longint):int64;inline;
28 var a2,a3,a4:int64;
29 begin
30 if l>r then exit(0);
31 if b[z]=1 then exit(0);
32 if (x=l) and (y=r) and (l=r) then
33 begin
34 a2:=a[z];
35 a[z]:=trunc(sqrt(a[z]));
36 if a[z]<=1 then b[z]:=1;
37 exit(a[z]-a2);
38 end;
39 a2:=op(z*2,x,(x+y) div 2,l,min((x+y) div 2,r));
40 a3:=op(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r);
41 a[z]:=a[z]+a2+a3;
42 if (b[z*2]=1) and (b[z*2+1]=1) then b[z]:=1;
43 exit(a2+a3);
44 end;
45 function cal(z,x,y,l,r:longint):int64;inline;
46 begin
47 if l>r then exit(0);
48 if (x=l) and (y=r) then exit(a[z]);
49 exit(cal(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2))+cal(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r));
50 end;
51 procedure swap(var x,y:longint);inline;
52 var z:longint;
53 begin
54 z:=x;x:=y;y:=z;
55 end;
56
57 begin
58 readln(n);
59 built(1,1,n);
60 readln;
61 readln(m);
62 for i:=1 to m do
63 begin
64 readln(j,k,l);
65 if k>l then swap(k,l);
66 case j of
67 1:writeln(cal(1,1,n,k,l));
68 0:op(1,1,n,k,l);
69 end;
70 end;
71 end.
72