Description
XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
"第一分钟，X说，要有数列，于是便给定了一个正整数数列。
第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。
Input
第一行一个整数n，代表数列中数的个数。
第二行n个正整数，表示初始状态下数列中的数。
第三行一个整数m，表示有m次操作。
接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。
Output
对于询问操作，每行输出一个回答。
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
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
7
6
这道题比较水(话说有人见过不算内存的lc大佬么。)心疼一发。对于1e12的数据就手动算了一发，发现6次就好了，就变成了1， 再怎么修改就无影响了，所以对线段树的修改操作来说就是判断当前节点代表区间[l,r]是否已全部变为1否则就暴力修改，然后就成了区间查询的裸题(话说在考场上没打build函数，被我一个全是询问的操作拍出来了。。好惊悚。。。)再心疼一发lc大佬
code：
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <stdio.h>
#define MAXN 100005
typedef long long ll;
using namespace std;
int need[MAXN],n,q;
ll a[MAXN],d[MAXN][7];
inline void divide(ll w,int id){
while(w!=1){
need[id]++;
w=sqrt(w);
d[id][need[id]]=w;
}
}
ll sum[MAXN<<3];
int change_time[MAXN];
void Maintain(int o){
sum[o]=sum[o<<1]+sum[o<<1|1];
}
void add(int o,int l,int r,int x,int y){
if(sum[o]!=r-l+1){
if(l==r){
change_time[l]++;
if(change_time[l]>need[l])sum[o]=1;
else sum[o]=d[l][change_time[l]];
return;
}
int m = l+r>>1;
if(x<=m)add(o<<1,l,m,x,y);
if(m<y)add(o<<1|1,m+1,r,x,y);
Maintain(o);
}
else return;
}
ll query(int o,int l,int r,int x,int y){
if(x<=l&&r<=y)return sum[o];
int m=l+r>>1;
ll ans=0;
if(x<=m)ans+=query(o<<1,l,m,x,y);
if(m<y)ans+=query(o<<1|1,m+1,r,x,y);
return ans;
}
void build(int o,int l,int r){
if(l==r){
sum[o]=a[l];
return;
}
int mid = l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
Maintain(o);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
divide(a[i],i);
}
build(1,1,n);
scanf("%d",&q);
while(q--){
int l,r,op;
scanf("%d%d%d",&op,&l,&r);
if(l>r)swap(l,r);
if(op==0)add(1,1,n,l,r);
else printf("%lld
",query(1,1,n,l,r));
}
}