题目背景
XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
题目描述
"第一分钟，X说，要有数列，于是便给定了一个正整数数列。
第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。
输入格式
第一行一个整数n，代表数列中数的个数。
第二行n个正整数，表示初始状态下数列中的数。
第三行一个整数m，表示有m次操作。
接下来mm行每行三个整数k,l,r，
k=0表示给[l,r]中的每个数开平方(下取整)k=1表示询问[l,r]中各个数的和。
数据中有可能l>rl>r，所以遇到这种情况请交换l和r。
输出格式
对于询问操作，每行输出一个回答。
输入输出样例
101 2 3 4 5 6 7 8 9 1050 1 101 1 101 1 50 5 81 4 8
1976
说明/提示
对于30%的数据，1$\le$ n,m $\le$ 1000，数列中的数不超过32767。
对于100%的数据，1$\le$ n,m $\le$ 100000，1$\le$ l,r$\le$ n，数列中的数大于0，且不超过1012。
注意l有可能大于r，遇到这种情况请交换l,r。
出现了第五种运算——开方，看来咱们的lazy标志不能用了qwq
但既然出在这肯定存在某种特殊的性质，可以是本身数的变化上，也可以是储存数据的变化上。
我们注意到开方是个好大好大的减小数的一种运算，而我们惊奇地发现1012只要做6次的开方就变成1了，所以就算是暴力全部开方，也最多只用操作六次，剩下的区间求和就是线段树拿手的啦。
我们储存一下区间的最大值来判断其是否大于1就可以去判断是否需要进行开方操作了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define MIN(a,b) (a)<(b)?(a):(b)10 #define MAX(a,b) (a)>(b)?(a):(b)11 #define ABS(a) (a)>0?(a):-(a)12 #define debug(a) printf("a=%d\n",a);13 #define fo(i,a,b) for (int i=(a);i<=(b);++i)14 #define fod(i,a,b) for (int i=(a);i>=(b);--i)15 #define re(i,a,b) for (int i=(a);i<(b);++i)16 #define red(i,a,b) for (int i=(a);i>(b);--i)17 #define M 10005018 #define N 40040019 typedef long long LL;20 using namespace std;21 LL a[M];22 struct Segment_Tree{23 LL maxx[N];24 LL sum[N];25 void build(LL root,LL l,LL r){26 if (l==r){27 maxx[root]=sum[root]=a[l];28 return;29 }30 LL mid=(l+r)>>1;31 build(root<<1,l,mid);32 build(root<<1|1,mid+1,r);33 maxx[root]=MAX(maxx[root<<1],maxx[root<<1|1]);34 sum[root]=sum[root<<1]+sum[root<<1|1];35 }36 LL get_sum(LL root,LL l,LL r,LL lef,LL righ){37 if (lef<=l&&righ>=r) return sum[root];38 LL mid=(l+r)>>1;39 LL qwq=0;40 if (lef<=mid) qwq+=get_sum(root<<1,l,mid,lef,righ);41 if (righ>mid) qwq+=get_sum(root<<1|1,mid+1,r,lef,righ);42 return qwq;43 }44 void updata(LL root,LL l,LL r,LL lef,LL righ){45 if (l==r){46 sum[root]=maxx[root]=sqrt(maxx[root]);47 return;48 }49 if (maxx[root]<=1) return;50 LL mid=(l+r)>>1;51 if (lef<=mid) updata(root<<1,l,mid,lef,righ);52 if (righ>mid) updata(root<<1|1,mid+1,r,lef,righ);53 maxx[root]=MAX(maxx[root<<1],maxx[root<<1|1]);54 sum[root]=sum[root<<1]+sum[root<<1|1];55 }56 }seg;57 int n,k,l,m,r;58 void readint(int &x){59 x=0;60 char c;61 int w=1;62 for (c=getchar();c<'0'||c>'9';c=getchar())63 if (c=='-') w=-1;64 for (;c>='0'&&c<='9';c=getchar())65 x=(x<<3)+(x<<1)+c-'0';66 x*=w;67 }68 void readlong(long long &x){69 x=0;70 char c;71 long long w=1;72 for (c=getchar();c<'0'||c>'9';c=getchar())73 if (c=='-') w=-1;74 for (;c>='0'&&c<='9';c=getchar())75 x=(x<<3)+(x<<1)+c-'0';76 x*=w;77 }78 int main(){79 readint(n);80 fo(i,1,n) readlong(a[i]);81 seg.build(1,1,n);82 readint(m);83 fo(i,1,m){84 readint(k);85 readint(l);86 readint(r);87 if (l>r) swap(l,r);88 if (k==0) seg.updata(1,1,n,l,r);89 else printf("%lld\n",seg.get_sum(1,1,n,l,r));90 }91 return 0;92 }