这题太坑了。。。满满的都是坑点
1号坑点：给定左右区间有可能是反的。。。因为题目上说x,y之间，但是没有说明x,y的大小关系（害我一直RE到怀疑人生）
2号坑点：开根号的和不等于和开根号（还好避开了）
3号坑点：当你明白了2号坑，你就会选择。。。单点更新，然后你就T飞了。其实一个1e18的数，开不了几次根就没了。。。所以修改多的情况下，大部分数很快降到1，当一个区间内部全是1，你还用一个个单点更新吗？所以就在2的基础上，加上如果这个区间的值的集合等于区间长度，直接返回，里面肯定全是1，还更新个屁啊。
4号坑点：当你觉得的自己稳了的时候，PE一发。。。末尾换行后再换行。。。WTF
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=;
LL a[maxn];
struct node{
int l,r;
LL val;
}tree[maxn<<];
LL sum;
inline int L(int r){return r<<;};
inline int R(int r){return r<<|;};
inline int MID(int l,int r){return (l+r)>>;};
void buildtree(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
tree[root].val=;
if (l==r){
tree[root].val=a[l];
return;
}
int mid=MID(l,r);
buildtree(L(root),l,mid);
buildtree(R(root),mid+,r);
tree[root].val=tree[L(root)].val+tree[R(root)].val;
}
void update(int root,int ul,int ur){
int l=tree[root].l;
int r=tree[root].r;
if (tree[root].val==r-l+){
return;
}
if (l==r){
tree[root].val=(LL)sqrt(tree[root].val);
return;
}
int mid=MID(l,r);
if (ur<=mid){
update(L(root),ul,ur);
}else if(ul>mid){
update(R(root),ul,ur);
}else {
update(L(root),ul,mid);
update(R(root),mid+,ur);
}
tree[root].val=tree[L(root)].val+tree[R(root)].val;
}
void query(int root,int ql,int qr){
int l=tree[root].l;
int r=tree[root].r;
if (ql<=l && r<=qr){
sum+=tree[root].val;
return;
}
int mid=MID(l,r);
if(qr<=mid){
query(L(root),ql,qr);
}else if(ql>mid){
query(R(root),ql,qr);
}else {
query(L(root),ql,mid);
query(R(root),mid+,qr);
}
}
int main(){
int n,m;
int cas=;
while(~scanf("%d",&n)){
printf("Case #%d:\n",cas++);
for (int i=;i<=n;i++){
scanf("%lld",&a[i]);
}
buildtree(,,n);
scanf("%d",&m);
int tmp1,tmp2,tmp3;
for (int i=;i<=m;i++){
scanf("%d%d%d",&tmp1,&tmp2,&tmp3);
if (tmp2>tmp3){
swap(tmp2,tmp3);
}
if(tmp1){
sum=;
query(,tmp2,tmp3);
printf("%lld\n",sum);
}else{
update(,tmp2,tmp3);
}
}
printf("\n");
}
return ;
}