上帝造题的七分钟 2 / 花神游历各国

形式化题目

有一个长度为 $n$ 的正整数数列 $a$ ，初始值给定。给出 $m$ 次操作：

对区间 $[l,r]$ 内的每个数执行 $a_i \leftarrow \lfloor \sqrt{a_i} \rfloor$ ；
询问区间 $[l,r]$ 内各数的和 $\sum_{i=l}^{r} a_i$ 。

要求按顺序处理全部操作并输出每次询问的答案。注意操作中可能出现 $l > r$ ，此时应交换两者。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 00:00
 * update_at: 2026-08-12 22:11
 */
// brute.cpp：小数据暴力解，直接逐元素开根号 / 求和，用来理解题意并辅助对拍。
// 本题是确定性模拟（每个位置独立开根号、独立求和），不是选/不选型选择序列，
// 所以用最直接的逐元素模拟写法，不适合用 01 序列递归枚举。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

long long a[MAXN]; // a[i] 表示第 i 个位置的当前值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cin >> m;
    while (m--) {
        int k, l, r;
        cin >> k >> l >> r;
        // 数据中有可能 l > r，遇到这种情况需要交换。
        if (l > r) swap(l, r);

        if (k == 0) {
            // 区间开根号：对区间内每个数独立执行一次下取整开方。
            for (int i = l; i <= r; i++) {
                a[i] = (long long)sqrt((double)a[i]);
            }
        } else {
            // 区间求和：暴力累加区间内的每个数。
            long long answer = 0;
            for (int i = l; i <= r; i++) {
                answer += a[i];
            }
            cout << answer << '\n';
        }
    }

    return 0;
}

brute.cpp 直接维护数组 a[]：区间开根号就逐个数开方，区间查询就逐个数累加，单次操作 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

关键观察有两点：

开方次数有限：每个数每开一次方就严格变小， $10^{12} \to 10^6 \to 10^3 \to 31 \to 5 \to 2 \to 1$ ，最多 6 次就收敛到 1；之后 $\lfloor \sqrt{1} \rfloor = 1$ 不再变化。
开方单调 + 最大值剪枝： $\lfloor \sqrt{x} \rfloor$ 单调不减，所以只要区间最大值 $\leqslant 1$ ，整段必然全是 0/1，开方是恒等变换，整段可以直接跳过。

于是用线段树，每个节点维护区间和 sum 与区间最大值 mx。开方操作进入节点时先剪枝：mx <= 1 直接返回；否则递归到叶子真正开方一次，回溯时 push_up 合并。开方不像区间翻转那样能靠摘要整段结算（ $\lfloor\sqrt{a}\rfloor + \lfloor\sqrt{b}\rfloor \neq \lfloor\sqrt{a+b}\rfloor$ ），所以这里没有懒标记，正确性完全由"最大值剪枝 + 叶子修改"保证，速度来自"每个叶子最多被改 6 次"的摊还。

数学视角：为什么没有懒标记也能快

懒标记成立的前提是"区间更新是摘要上的自同态"，比如翻转能用 len - sum 结算。而开方不是：它依赖区间内每个元素的具体值。但它有两个更弱的性质，恰好够用：

单调性： $x \leqslant y \Rightarrow \lfloor\sqrt{x}\rfloor \leqslant \lfloor\sqrt{y}\rfloor$ 。所以最大值是最省信息的剪枝依据：最大值都不超过 1，整段就不用动。
势能下降：定义势能为"区间内仍大于 1 的元素个数"。每次真正修改一个叶子，该位置的势能严格减 1（最多减 6 次到 0）。所有操作的总势能下降是 $O(n)$ ，每个势能单位花费 $O(\log n)$ 的树链代价，这就是摊还复杂度的来源。

以样例为例，每次操作后的真实数列如下：

操作	数列 1…10	输出
初始	1 2 3 4 5 6 7 8 9 10
0 1 10	1 1 1 2 2 2 2 2 3 3
1 1 10		19
1 1 5		7
0 5 8	1 1 1 2 1 1 1 1 3 3
1 4 8		6

这张表对应 in1 的完整执行过程：开方后每个大于 1 的位置都严格变小（如 5,6,7,8 从 2 变 1），查询输出和。观察两次查询：整段开方后和从 19 降到 15， $[1,5]$ 的和 7、 $[4,8]$ 的和 6，均与输出一致。

再看大数收敛过程（这是"6 次到 1"的直接证据）：

开方次数	0	1	2	3	4	5	6
值	$10^{12}$	$10^6$	$10^3$	31	5	2	1

每一列是上一列开一次根号的结果： $\lfloor \sqrt{10^{12}} \rfloor = 10^6$ ， $\lfloor \sqrt{31} \rfloor = 5$ ，等等。6 次之后停在 1，这就是"每个叶子最多被真正修改约 6 次"的来源。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 00:00
 * update_at: 2026-08-15 22:40
 */
// main.cpp：区间开根号（下取整）+ 区间求和。
// 线段树节点维护区间和与最大值，最大值 <= 1 时剪枝跳过整段，不需要懒标记。
#include <bits/stdc++.h>
using namespace std;

// 计算 x 的下取整平方根。
// double 开方可能有一点点误差，用两次乘法把结果校正到正确区间。
long long isqrt_safe(long long x) {
    long long r = (long long)sqrt((double)x);
    while ((r + 1) * (r + 1) <= x) r++;
    while (r * r > x) r--;
    return r;
}

// 区间开方 + 区间求和线段树（最大值剪枝，无懒标记）
struct SegmentTreeSqrt {
    using T = long long;

    // 线段树节点：sum 为区间和，mx 为区间最大值
    struct Node {
        T sum = 0;    // 当前区间的区间和
        T mx = 0;     // 当前区间的最大值

        // 合并两个孩子：和相加，最大值取较大者
        Node operator+(const Node &other) const {
            return Node{sum + other.sum, max(mx, other.mx)};
        }
    };

    // 左儿子 / 右儿子的节点编号
    static int lson(int p) { return p << 1; }
    static int rson(int p) { return p << 1 | 1; }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    int n = 0;              // 区间大小
    vector<Node> tree;      // 线段树数组

    SegmentTreeSqrt(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{});
    }

    // 上推：用两个孩子合并出当前节点
    void push_up(int p) {
        tree[p] = tree[lson(p)] + tree[rson(p)];
    }

    // 用数组 a 建树
    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p].sum = tree[p].mx = a[l];
            return;
        }
        int m = mid(l, r);
        build(a, l, m, lson(p));
        build(a, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间开方：把 [ql, qr] 内每个数执行一次下取整开方。
    // 剪枝：开方单调不减，区间最大值不超过 1 时整段全是 0/1，开方后不变，直接跳过。
    void sqrt_update(int ql, int qr, int l, int r, int p = 1) {
        if (tree[p].mx <= 1) return;

        if (l == r) {
            // 真正落到叶子，执行一次开方并同步最大值。
            tree[p].sum = tree[p].mx = isqrt_safe(tree[p].sum);
            return;
        }

        int m = mid(l, r);
        if (ql <= m) sqrt_update(ql, qr, l, m, lson(p));
        if (qr > m) sqrt_update(ql, qr, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间查询：[ql, qr] 的区间和
    T query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p].sum;

        int m = mid(l, r);
        T answer = 0;
        if (ql <= m) answer += query(ql, qr, l, m, lson(p));
        if (qr > m) answer += query(ql, qr, m + 1, r, rson(p));
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTreeSqrt seg(n);
    seg.build(a, 1, n);

    cin >> m;
    while (m--) {
        int k, l, r;
        cin >> k >> l >> r;
        // 数据中有可能 l > r，遇到这种情况需要交换。
        if (l > r) swap(l, r);
        if (k == 0)
            seg.sqrt_update(l, r, 1, n); // 区间开根号
        else
            cout << seg.query(l, r, 1, n) << '\n'; // 区间求和
    }

    return 0;
}

复杂度

时间：单次查询 $O(\log n)$ ；开方操作有剪枝，每个叶子最多被真正修改 $O(\log \log A)$ （ $A \leqslant 10^{12}$ 时至多 6 次），摊还总复杂度 $O((n+m) \log n + n \log n \log \log A)$ 。
空间：线段树四倍数组（sum、mx）， $O(n)$ 。

总结

这类"区间操作快速收敛"的题（开根号、整除、取模）统一套路：维护区间最值做剪枝，整段已收敛就跳过，真正修改只在叶子发生，复杂度由"每个位置被改次数有限"来摊还。它和区间翻转/赋值不同——后者靠懒标记整段结算，前者没有摘要自同态，只能靠势能下降剪枝。rbook 的《线段树：区间赋值与区间查询》讲解了本解使用的 push_up / build / query 模板结构（segtree-range-assign），本解在此基础上把"区间赋值"替换为"最大值剪枝 + 叶子开方"，并去掉了懒标记。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  对 [l,r] 逐个数开根号 / 逐个数求和      O(n) 每次操作
        |
        | 瓶颈：开方无法像翻转那样整段结算（依赖每个位置的值），
        |       逐个数访问导致单次 O(n)、总 O(n*m)
        v
关键观察
  开方次数有限：x -> floor(sqrt(x)) 严格变小，10^12 最多 6 次到 1
  开方单调不减：区间最大值 <= 1 时整段开方恒等，可以直接跳过
        |
        v
线段树 + 最大值剪枝（main.cpp）
  节点存区间和 sum 与区间最大值 mx
  开方：mx <= 1 直接返回（剪枝），否则递归到叶子真正开一次方
  查询：整段命中返回 sum，否则递归累加
        |
        v
摊还复杂度 O((n + m) log n)，空间 O(n)

图中三条主线分别对应"暴力在哪里慢"“观察到什么性质”“正式解如何利用这个性质”。核心是第二行：开方把每个位置"快速推向收敛点 1"，mx <= 1 的剪枝把所有已收敛的区间挡在节点层，因此整道题没有一次操作需要访问"仍有意义的"叶子之外的区域。