这题太坑了。。。满满的都是坑点
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=100010; LL a[maxn]; struct node{ int l,r; LL val; }tree[maxn<<2]; LL sum; inline int L(int r){return r<<1;}; inline int R(int r){return r<<1|1;}; inline int MID(int l,int r){return (l+r)>>1;}; void buildtree(int root,int l,int r){ tree[root].l=l; tree[root].r=r; tree[root].val=0; if (l==r){ tree[root].val=a[l]; return; } int mid=MID(l,r); buildtree(L(root),l,mid); buildtree(R(root),mid+1,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+1){ 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+1,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+1,qr); } } int main(){ int n,m; int cas=1; while(~scanf("%d",&n)){ printf("Case #%d: ",cas++); for (int i=1;i<=n;i++){ scanf("%lld",&a[i]); } buildtree(1,1,n); scanf("%d",&m); int tmp1,tmp2,tmp3; for (int i=1;i<=m;i++){ scanf("%d%d%d",&tmp1,&tmp2,&tmp3); if (tmp2>tmp3){ swap(tmp2,tmp3); } if(tmp1){ sum=0; query(1,tmp2,tmp3); printf("%lld ",sum); }else{ update(1,tmp2,tmp3); } } printf(" "); } return 0; }