问题分析

• 修改：将区间内的每个数开平方。
• 查询：求区间和。
  需要高效处理这些操作，线段树是合适的数据结构。

线段树设计

• 节点结构：每个节点存储区间[l, r]的元素个数和和值。
• 操作处理：
  • 修改操作：递归更新叶子节点，并向上更新和值。
  • 查询操作：递归查询区间和，返回结果。

优化思路

• 递归优化：减少重复计算，避免超时。
• 平方根处理：数值逐渐变小，减少计算量。
• 提前终止：当区间元素全部为1时，停止修改操作。

实现细节

• 构建函数：初始化叶子节点值，并合并上级节点和值。
• 修改函数：处理叶子节点，递归更新区间。
• 查询函数：递归查询区间和，返回结果。

伪代码实现

#include 
    
     
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
const int N = 1E5 + 10;
ll w[N];
struct node {
    int l, r;
    ll val;
} t[N << 2];
void pushdown(node &op) {
    op.val = sqrt(op.val);
}
void pushup(int x) {
    t[x].val = t[x << 1].val + t[(x << 1) | 1].val;
}
void build(int l, int r, int x = 1) {
    t[x] = {l, r, w[l]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
void modify(int l, int r, int x = 1) {
    if (t[x].val == t[x].r - t[x].l + 1) return;
    if (t[x].l == t[x].r) {
        pushdown(t[x]);
        return;
    }
    int mid = t[x].l + t[x].r >> 1;
    if (l <= mid) modify(l, r, x << 1);
    if (r > mid) modify(l, r, x << 1 | 1);
    pushup(x);
}
ll ask(int l, int r, int x = 1) {
    if (l <= t[x].l && r >= t[x].r) return t[x].val;
    int mid = t[x].l + t[x].r >> 1;
    ll res = 0;
    if (l <= mid) res += ask(l, r, x << 1);
    if (r > mid) res += ask(l, r, x << 1 | 1);
    return res;
}
int main() {
    int T = 1;
    while (scanf("%d", &n) != EOF) {
        rep(i, n) {
            scanf("%lld", &w[i]);
        }
        build(1, n);
        printf("Case #%d:\n", T++);
        scanf("%d", &m);
        while (m--) {
            int op, l, r;
            scanf("%d %d %d", &op, &l, &r);
            if (l > r) swap(l, r);
            if (op) {
                printf("%lld\n", ask(l, r));
            } else {
                modify(l, r);
            }
        }
        printf("\n");
    }
    return 0;
}
    

注意事项

• 输入处理：确保输入正确，不会影响结果。
• 优化措施：减少重复计算，提高运行效率。