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

【題目敘述】https://vjudge.net/problem/HDU-4027
【解題想法】線段樹 (Segment Tree) + 剪枝 (Pruning)

• long long total[100005 << 2], mx[100005 << 2]; 開 4 倍陣列。
• 線段樹的每個節點，除了紀錄區間和之外，也紀錄區間最大值。
• 剪枝：每次進行update( )時，當 mx[x] == 1，不動作。因為 sqrt(1) = 1，不影響結果。
```#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 > 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";
}
}
```