Can you answer these queries?(線分ツリーの単点更新)


萌えるトランスポートドア
1つのlong long範囲内の数の開方は10回を超えないため、テーマは線分ツリーの単点更新問題に転化する.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <cstdlib>
#include <algorithm>

#define ls u << 1
#define rs u << 1 | 1
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
const int M = 1e5 + 100;
const int N = 1e7 + 100;
ll sum[M << 2];

void pushup(int u){
    sum[u] = sum[ls] + sum[rs];
}

void build(int l,int r,int u){
    if(l == r){
        scanf("%I64d",sum + u);
    }
    else {
        int mid = (l + r) >> 1;
        build(lson);
        build(rson);
        pushup(u);
    }
}

void update(int L,int R,int l,int r,int u){
    if(sum[u] == (r - l + 1)){
        return;
    }
    if(l == r){
        sum[u] = floor(sqrt((double)sum[u]));
    }
    else {
        int mid = (l + r) >> 1;
        if(L <= mid) update(L,R,lson);
        if(R > mid) update(L,R,rson);
        pushup(u);
    }
}

ll query(int L,int R,int l,int r,int u){
    if(L <= l && R >= r){
        return sum[u];
    }
    else {
        int mid = (l + r) >> 1;
        ll res = 0;
        if(L <= mid) res += query(L,R,lson);
        if(R > mid) res += query(L,R,rson);
        return res;
    }
}

int main(){
    //freopen("in","r",stdin);
    int n,m,cnt = 0;
    while(~scanf("%d",&n)){
        build(1,n,1);
        scanf("%d",&m);
        printf("Case #%d:
",++cnt); while(m--){ int t,l,r; scanf("%d %d %d",&t,&l,&r); if(l > r) swap(l,r); if(!t) update(l,r,1,n,1); else { printf("%I64d
",query(l,r,1,n,1)); } } puts(""); } return 0; }