Can you answer these queries?：線段樹單點更新 (平方根序列)

題目大意

數組 A 支持兩種操作：

1. 區間開方：將 [L,R] 內每個元素替換為 `floor(sqrt(x))`。
2. 區間求和：查詢 [L,R] 元素和。

n, m ≤ 1e5。元素值 64 位整數。

核心觀察

64 位整數反覆開方最多 **6-7 次** 變為 0 或 1 (之後不再變化)。因此每個位置被更新的次數極少，總更新次數上界為 O(n log log MAX)。

線段樹優化策略

• 節點維護：`sum` (區間和)，`mx` (區間最大值)。
• 若節點 `mx <= 1`，說明區間內所有元素已穩定 (0 或 1)，**直接返回跳過更新**。
• 遞歸更新到葉子節點執行 `x = floor(sqrt(x))`，回溯更新 `sum` 和 `mx`。
• 查詢標準區間求和。

代碼實現 (C++)

#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int MAXN = 100005;

struct Node { ll sum; int mx; } tree[MAXN << 2];
ll a[MAXN];

void pushup(int rt) {
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
    tree[rt].mx = max(tree[rt<<1].mx, tree[rt<<1|1].mx);
}

void build(int rt, int l, int r) {
    if (l == r) { tree[rt].sum = tree[rt].mx = a[l]; return; }
    int mid = (l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int L, int R) {
    if (tree[rt].mx <= 1) return; // 已穩定，剪枝
    if (l == r) {
        tree[rt].sum = tree[rt].mx = (int)sqrt((double)tree[rt].mx);
        return;
    }
    int mid = (l+r)>>1;
    if (L <= mid) update(rt<<1, l, mid, L, R);
    if (R > mid) update(rt<<1|1, mid+1, r, L, R);
    pushup(rt);
}

ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[rt].sum;
    int mid = (l+r)>>1;
    ll res = 0;
    if (L <= mid) res += query(rt<<1, l, mid, L, R);
    if (R > mid) res += query(rt<<1|1, mid+1, r, L, R);
    return res;
}

int main() {
    int n, m, cas = 0;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        build(1, 1, n);
        scanf("%d", &m);
        printf("Case #%d:\n", ++cas);
        while (m--) {
            int op, l, r; scanf("%d%d%d", &op, &l, &r);
            if (l > r) swap(l, r);
            if (op == 0) update(1, 1, n, l, r);
            else printf("%lld\n", query(1, 1, n, l, r));
        }
        puts("");
    }
    return 0;
}

複雜度分析

• 建樹：O(n)
• 單次更新：均攤 O(log n) (因每個葉子最多更新 ~6 次)
• 查詢：O(log n)
• 總體：O((n + m) log n) 且常數極小。

關鍵技巧

利用數值性質 (`sqrt` 收斂快) 將區間更新轉化為「只有少數節點真正需要更新」的稀疏更新問題，線段樹 `mx` 剪枝是核心。