Can you answer these queries?

题目

给定N个元素，操作M次区间修改和区间查询，区间修改是把区间内所有元素各自进行开方，区间查询是查询这个区间的和。初始元素小于

分析

对于此题，开方的操作是很难上下传递的，而我们知道开方速度是很快的，我测了一下1e18开方只需要6次，所以我们完全可以使用暴力来修改，假如全都修改到了1，也就6*1e5的样子。对于区间和已经等于区间长度的，就不再往下递归进行修改了，因为没必要。

坑点

输入的区间不一定是前者小于后者
每一组输出要多输出一个空行

AC代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const ll maxn = 1e5+10;

ll N,M;
struct node{
    ll l,r,sum;
}tr[4*maxn];
ll arr[maxn];
void pushup(ll u){
    node &fa = tr[u],&L = tr[u*2],&R = tr[u*2+1];
    fa.sum = L.sum + R.sum;
}

void build(ll u,ll l,ll r){
    if(l == r) tr[u] = {l,r,arr[l]};
    else{
        tr[u]  = {l,r};
        ll mid = l+r>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
    }
}
void modify(ll u,ll l,ll r){
    if(tr[u].l>=l && tr[u].r<=r){
        if(tr[u].r-tr[u].l+1 == tr[u].sum) return ;//不用再递归了
        if(tr[u].r == tr[u].l) {
            tr[u].sum = arr[tr[u].l] = sqrt(arr[tr[u].l]);
        }else{
            modify(u*2,l,r);
            modify(u*2+1,l,r);
            pushup(u);
        }
    }else{
        int mid = (tr[u].l+tr[u].r)>>1;
        if(l<=mid) modify(u*2,l,r);
        if(r>mid) modify(u*2+1,l,r);
        pushup(u);
    }
}
ll query(ll u,ll l,ll r){
    if(tr[u].l>=l && tr[u].r<=r){
        return tr[u].sum;
    }else{
        int mid = (tr[u].l+tr[u].r)>>1;
        ll sum = 0;
        if(l<=mid) sum += query(u*2,l,r);
        if(r>mid) sum += query(u*2+1,l,r);
        return sum;
    }
}
int main(){
    int kase = 0;
    while(scanf("%lld",&N) != EOF){
        printf("Case #%d:\n",++kase);
        for(int i = 1;i<=N;i++) scanf("%lld",&arr[i]);
        build(1,1,N);
        cin>>M;
        ll t,a,b;
        while(M--){
            scanf("%lld %lld %lld",&t,&a,&b);
            if(a>b) swap(a,b);
            if(t == 0){
                modify(1,a,b);
            }else{
                printf("%lld\n",query(1,a,b));
            }
        }
        puts("");
    }
    return 0;
}