Description

XLk覺得《上帝造題的七分鐘》不太過癮，于是有了第二部。
“第一分鐘，X說，要有數(shù)列，于是便給定了一個(gè)正整數(shù)數(shù)列。
第二分鐘，L說，要能修改，于是便有了對一段數(shù)中每個(gè)數(shù)都開平方(下取整)的操作。
第三分鐘，k說，要能查詢，于是便有了求一段數(shù)的和的操作。
第四分鐘，彩虹喵說，要是NOIP難度，于是便有了數(shù)據(jù)范圍。
第五分鐘，詩人說，要有韻律，于是便有了時(shí)間限制和內(nèi)存限制。
第六分鐘，和雪說，要省點(diǎn)事，于是便有了保證運(yùn)算過程中及最終結(jié)果均不超過64位有符號(hào)整數(shù)類型的表示范圍的限制。
第七分鐘，這道題終于造完了，然而，造題的神牛們再也不想寫這道題的程序了?！?/span>
——《上帝造題的七分鐘·第二部》
所以這個(gè)神圣的任務(wù)就交給你了。

Input

第一行一個(gè)整數(shù)n，代表數(shù)列中數(shù)的個(gè)數(shù)。
第二行n個(gè)正整數(shù)，表示初始狀態(tài)下數(shù)列中的數(shù)。
第三行一個(gè)整數(shù)m，表示有m次操作。
接下來m行每行三個(gè)整數(shù)k,l,r，k=0表示給[l,r]中的每個(gè)數(shù)開平方(下取整)，k=1表示詢問[l,r]中各個(gè)數(shù)的和。

Output

對于詢問操作，每行輸出一個(gè)回答。

Sample Input

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

Sample Output

19
7
6

HINT

?

1：對于100%的數(shù)據(jù)，1<=n<=100000，1<=l<=r<=n，數(shù)列中的數(shù)大于0，且不超過1e12。
2：數(shù)據(jù)不保證L<=R 若L>R，請自行交換L,R，謝謝！

?

?

其實(shí)就是就是如果一個(gè)結(jié)點(diǎn)值為0或者1就不再更新；如果一棵樹左右兒子都不再更新，它也不再更新。

代碼:

1 type node=record 2 l,r:longint; 3 num:int64; 4 tag:boolean; 5 end; 6 7 var 8 f:array[1..500000]of node; 9 a:array[1..100000]of int64; 10 n,m,i,k,x,y:longint; 11 12 procedure swap(var x,y:longint); 13 var 14 t:longint; 15 begin 16 t:=x; x:=y; y:=t; 17 end; 18 19 procedure build(h,l,r:longint); 20 begin 21 f[h].l:=l; f[h].r:=r; 22 if l=r then 23 begin 24 f[h].num:=a[l]; 25 if (a[l]=0)or(a[l]=1) then f[h].tag:=true; 26 exit; 27 end; 28 build(h*2,l,(l+r) div 2); 29 build(h*2+1,(l+r) div 2+1,r); 30 f[h].num:=f[h*2].num+f[h*2+1].num; 31 f[h].tag:=f[h*2].tag and f[h*2+1].tag; 32 end; 33 34 procedure change(h,l,r:longint); 35 begin 36 if f[h].tag then exit; 37 if f[h].l=f[h].r then 38 begin 39 f[h].num:=trunc(sqrt(f[h].num)); 40 if (f[h].num=0)or(f[h].num=1) then f[h].tag:=true; 41 exit; 42 end; 43 if l<=f[h*2].r then change(h*2,l,r); 44 if r>=f[h*2+1].l then change(h*2+1,l,r); 45 f[h].num:=f[h*2].num+f[h*2+1].num; 46 f[h].tag:=f[h*2].tag and f[h*2+1].tag; 47 end; 48 49 function find(h,l,r:longint):int64; 50 begin 51 find:=0; 52 if (f[h].l>=l)and(f[h].r<=r) then exit(f[h].num); 53 if l<=f[h*2].r then inc(find,find(h*2,l,r)); 54 if r>=f[h*2+1].l then inc(find,find(h*2+1,l,r)); 55 end; 56 57 begin 58 readln(n); 59 for i:=1 to n do read(a[i]); 60 build(1,1,n); 61 readln(m); 62 for i:=1 to m do 63 begin 64 readln(k,x,y); 65 if x>y then swap(x,y); 66 if k=0 then change(1,x,y) 67 else writeln(find(1,x,y)); 68 end; 69 end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/kry-ssw-1314/p/4635921.html

總結(jié)

以上是生活随笔為你收集整理的【暑假训练 7.10】 codevs 2492 上帝造题的七分钟2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。