【題解】HDU 4027. Can you answer these queries?

#include <iostream>
#include <cmath>
using namespace std;

int n, m, Case, t, x, y;
long long total[100005 << 2], mx[100005 << 2];

void pull(int x){
    total[x] = total[x<<1] + total[x<<1|1];
    mx[x] = max(mx[x<<1], mx[x<<1|1]);
}

void build(int x, int l, int r){
    if (l == r){
        cin >> total[x];
        mx[x] = total[x];
        return;
    }
    int mid = (l + r) >> 1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    pull(x);
}

long long query(int x, int l, int r, int ql, int qr){
    if (ql <= l && r <= qr) return total[x];
    if (ql > r || qr < l) return 0;
    int mid = (l + r) >> 1;
    return query(x<<1, l, mid, ql, qr) + query(x<<1|1, mid+1, r, ql, qr);
}

void update(int x, int l, int r, int ul, int ur){
    if (l == r){
        total[x] = (long long)sqrt(total[x]);
        mx[x] = total[x];
        return;
    }
    if (mx[x] == 1) return;
    int mid = (l + r) >> 1;
    if (ul <= mid) update(x<<1, l, mid, ul, ur);
    if (ur > mid) update(x<<1|1, mid+1, r, ul, ur);
    pull(x);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n){
        Case++;
        cout << "Case #" << Case << ":\n";
        build(1, 1, n);
        cin >> m;
        for (int i = 0; i < m; i++){
            cin >> t >> x >> y;
            if (x > y) swap(x, y);
            if (t == 0){
                update(1, 1, n, x, y);
            }else{
                cout << query(1, 1, n, x, y) << "\n";
            }
        }
        cout << "\n";
    }
}