「一本通 4.3 练习 2」花神游历各国

形式化题目

给定长度为 $n$ 的整数序列 $a[1..n]$ （ $0 \leqslant a_i \leqslant 10^9$ ），支持两类操作：

1 l r：输出区间和 $\sum_{i=l}^{r} a[i]$ ；
2 l r：对每个 $i \in [l, r]$ ，令 $a[i] \gets \lfloor\sqrt{a[i]}\rfloor$ （向下取整）。

以题面样例（ $a = [1, 100, 5, 5]$ ）逐操作推演，表格中"处理后序列"是该操作执行完后的状态：

序号	操作	处理后序列 $a$	本步输出
1	`1 1 2`	$[1,\ 100,\ 5,\ 5]$	$1 + 100 = 101$
2	`2 1 2`	$[1,\ 10,\ 5,\ 5]$	—
3	`1 1 2`	$[1,\ 10,\ 5,\ 5]$	$1 + 10 = 11$
4	`2 2 3`	$[1,\ 3,\ 2,\ 5]$	—
5	`1 1 4`	$[1,\ 3,\ 2,\ 5]$	$1 + 3 + 2 + 5 = 11$

关键取值： $\lfloor\sqrt{100}\rfloor = 10$ 、 $\lfloor\sqrt{10}\rfloor = 3$ 、 $\lfloor\sqrt{5}\rfloor = 2$ 。三次询问依次输出 $101$ 、 $11$ 、 $11$ ：第 3 步时 $a[1]$ 仍是 1（开方不变），第 5 步时整个数组已经是 $[1, 3, 2, 5]$ 。

正解

思路

1. 朴素做法与其瓶颈

对每次 2 l r 逐点开方、每次 1 l r 逐点求和，单次 $O(n)$ ，总计 $O(nm) = 2 \times 10^{10}$ ，必然超时。

把求和侧换成线段树只能救一半：开方是一种非线性操作，打不了统一的懒标记—— $\lfloor\sqrt{x+y}\rfloor \neq \lfloor\sqrt{x}\rfloor + \lfloor\sqrt{y}\rfloor$ （例如 $\lfloor\sqrt{4+4}\rfloor = 2$ ，而 $\lfloor\sqrt{4}\rfloor + \lfloor\sqrt{4}\rfloor = 4$ ），所以"整段加一个标记、用时下推"的经典套路在这里失效。瓶颈变成：区间开方怎样只在"还会变的值"上花时间。

2. 关键观察：值自己会停下来

$10^9$ 以内的值反复开方，很快收敛到 0/1，之后开方不再产生任何变化：

起始值	开方链（向下取整）	实际变化次数
$10^9$	$10^9 \to 31622 \to 177 \to 13 \to 3 \to 1$	5
$10^5$	$100000 \to 316 \to 17 \to 4 \to 2 \to 1$	5
$100$	$100 \to 10 \to 3 \to 1$	3
$0$ 或 $1$	$v \to v$	0

因此单个值至多变化 5 次就永久停住，全部操作中值的变化总次数不超过 $5n$ ——只要让每次区间开方的代价与"真正变化的值的个数"挂钩，总时间就可控。

3. 线段树设计

线段树每个节点维护三元组 $[$ 区间和, 区间最大值, 区间最小值 $]$ ：

询问：标准线段树区间求和， $O(\log n)$ ；
区间开方递归时按三种情况处理：
1. 与操作区间无交，或 $\max \leqslant 1$ ：直接返回——段内只有 0/1，开方不改变任何值，整棵子树跳过；
2. 整段被操作区间覆盖且 $\max = \min$ ：全段同值 $v$ ，一次改写为 $\lfloor\sqrt{v}\rfloor$ （和记为 $\lfloor\sqrt{v}\rfloor \times$ 段长），不下探；
3. 其余情况：只递归真正有交的孩子，回溯时用孩子刷新父节点三元组。

$\max$ 与 $\min$ 正好充当"还需不需要动手"的探测器： $\max \leqslant 1$ 说明整段已经停住， $\max = \min$ 说明整段可以一步改写，一次改写对应段内每个值都在变化，其总次数被第 2 节的 $5n$ 限制住。

4. 一个必须处理的坑：同值标记的同步

情况 2 只改写了当前内部节点，它的孩子仍保留开方前的旧值——"整段同值"本质上是一个还没下推的标记。之后若再下探到这些陈旧孩子，就会读到错误的值（真实数据上最初的实现正是因此 9/10 组不一致）。两条配套规则保证任何被读到的节点都与真实状态一致：

查询遇到 $\max = \min$ 的部分重叠节点时不下探，直接用 $v \times$ 重叠长度作答；
更新要下探进 $\max = \min$ 的节点（只被部分覆盖时），先把同值下推给两个孩子（代码中的 push_equal），恢复一致后再递归。

因为"节点与孩子不同步"只可能发生在 $\max = \min$ 的节点上，而每次下探前总是先同步，归纳可得：所有被读到的三元组都等于其真实子区间的状态。

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 17:38
# update_at: 2026-09-30 17:38

import sys
from math import isqrt

# 线段树每个节点存 [区间和, 区间最大值, 区间最小值]，下标 1 起
SUM, MX, MN = 0, 1, 2


def build(node: int, lo: int, hi: int, arr: list[int], t: list[list[int]]) -> None:
    """建树：叶子存单个国家的喜欢度，父节点由孩子合并。"""
    if lo == hi:
        v = arr[lo - 1]
        t[node][SUM] = t[node][MX] = t[node][MN] = v
        return
    mid = (lo + hi) // 2
    build(node << 1, lo, mid, arr, t)
    build(node << 1 | 1, mid + 1, hi, arr, t)
    pull(node, t)


def pull(node: int, t: list[list[int]]) -> None:
    """用两个孩子刷新父节点的 [和, 最大, 最小]。"""
    a, b = t[node << 1], t[node << 1 | 1]
    p = t[node]
    p[SUM] = a[SUM] + b[SUM]
    p[MX] = a[MX] if a[MX] > b[MX] else b[MX]
    p[MN] = a[MN] if a[MN] < b[MN] else b[MN]


def push_equal(node: int, lo: int, hi: int, t: list[list[int]]) -> None:
    """把父亲"整段同值"的标记下推给两个孩子，恢复孩子与父亲的一致。

    整段开方可能只改了内部节点，孩子还是开方前的旧值；下次要下探时必须先补齐。
    """
    v = t[node][MX]
    mid = (lo + hi) // 2
    left, right = t[node << 1], t[node << 1 | 1]
    left[SUM], left[MX], left[MN] = v * (mid - lo + 1), v, v
    right[SUM], right[MX], right[MN] = v * (hi - mid), v, v


def apply_sqrt(node: int, lo: int, hi: int, ql: int, qr: int, t: list[list[int]]) -> None:
    """区间开方取整：无交、或整段已是 0/1 时返回；全相等的整段一次改完。"""
    p = t[node]
    if hi < ql or lo > qr or p[MX] <= 1:  # 0 和 1 开方后不变，整棵子树跳过
        return
    if p[MX] == p[MN]:  # 整段同值：全盖住就地开方，否则先下推再下探
        if ql <= lo and hi <= qr:
            v = isqrt(p[MX])
            p[SUM], p[MX], p[MN] = v * (hi - lo + 1), v, v
            return
        push_equal(node, lo, hi, t)
    mid = (lo + hi) // 2
    if ql <= mid:  # 只下探真正有交的孩子，省掉一次空递归
        apply_sqrt(node << 1, lo, mid, ql, qr, t)
    if qr > mid:
        apply_sqrt(node << 1 | 1, mid + 1, hi, ql, qr, t)
    pull(node, t)


def query(node: int, lo: int, hi: int, ql: int, qr: int, t: list[list[int]]) -> int:
    """区间求和：完全落入取区间和；同值段按重叠长度直接算，否则递归两侧。"""
    p = t[node]
    if ql <= lo and hi <= qr:
        return p[SUM]
    if p[MX] == p[MN]:  # 部分重叠的同值段：孩子可能没同步，不必下探
        return p[MX] * (min(hi, qr) - max(lo, ql) + 1)
    mid = (lo + hi) // 2
    total = 0
    if ql <= mid:
        total = query(node << 1, lo, mid, ql, qr, t)
    if qr > mid:
        total += query(node << 1 | 1, mid + 1, hi, ql, qr, t)
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    arr = [next(data) for _ in range(n)]  # 各国初始喜欢度
    t = [[0, 0, 0] for _ in range(n << 2)]
    build(1, 1, n, arr, t)

    out: list[str] = []
    m = next(data)
    for _ in range(m):
        x, l, r = next(data), next(data), next(data)
        if x == 1:  # 询问 l..r 的开心值总和
            out.append(str(query(1, 1, n, l, r, t)))
        else:  # l..r 每个国家的喜欢度开方取整
            apply_sqrt(1, 1, n, l, r, t)

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 07:39
 * update_at: 2026-10-05 07:39
 */
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

// 题目数据规模：n <= 1e5，线段树开 4n 个节点
const int MAXN = 100005;
const int MAXNODE = MAXN << 2;

int n, m;
ll delta[MAXN]; // delta[i] = 第 i 个国家的初始喜欢度

// 线段树每个节点维护三元组 [区间和, 区间最大值, 区间最小值]
ll tsum[MAXNODE];
ll tmax[MAXNODE];
ll tmin[MAXNODE];

// 建树：叶子存单个国家的喜欢度，父节点由两个孩子合并
void build(int node, int lo, int hi) {
    if (lo == hi) {
        tsum[node] = tmax[node] = tmin[node] = delta[lo];
        return;
    }
    int mid = (lo + hi) >> 1;
    build(node << 1, lo, mid);
    build(node << 1 | 1, mid + 1, hi);
    // 用孩子刷新父节点三元组
    tsum[node] = tsum[node << 1] + tsum[node << 1 | 1];
    tmax[node] = max(tmax[node << 1], tmax[node << 1 | 1]);
    tmin[node] = min(tmin[node << 1], tmin[node << 1 | 1]);
}

// 把"整段同值"的状态下推给两个孩子，恢复孩子与父亲的一致。
// 整段开方可能只改写了内部节点，孩子还是开方前的旧值；要下探时必须先补齐。
void push_equal(int node, int lo, int hi) {
    ll v = tmax[node];
    int mid = (lo + hi) >> 1;
    tsum[node << 1] = v * (mid - lo + 1);
    tmax[node << 1] = tmin[node << 1] = v;
    tsum[node << 1 | 1] = v * (hi - mid);
    tmax[node << 1 | 1] = tmin[node << 1 | 1] = v;
}

// 区间 [ql, qr] 每个值开方取整：
// 无交、或 max <= 1 时整棵子树跳过（0/1 开方不变）；
// 整段同值且全盖住时一次改完，否则先下推同值再递归。
void apply_sqrt(int node, int lo, int hi, int ql, int qr) {
    if (hi < ql || lo > qr || tmax[node] <= 1) return;
    if (tmax[node] == tmin[node]) {
        if (ql <= lo && hi <= qr) { // 全盖住：整段同值 v，一次改写为 sqrt(v)
            ll v = (ll)sqrt((double)tmax[node]);
            tsum[node] = v * (hi - lo + 1);
            tmax[node] = tmin[node] = v;
            return;
        }
        push_equal(node, lo, hi); // 部分覆盖：先同步孩子再下探
    }
    int mid = (lo + hi) >> 1;
    if (ql <= mid) apply_sqrt(node << 1, lo, mid, ql, qr);
    if (qr > mid) apply_sqrt(node << 1 | 1, mid + 1, hi, ql, qr);
    // 回溯时用孩子刷新父节点三元组
    tsum[node] = tsum[node << 1] + tsum[node << 1 | 1];
    tmax[node] = max(tmax[node << 1], tmax[node << 1 | 1]);
    tmin[node] = min(tmin[node << 1], tmin[node << 1 | 1]);
}

// 区间 [ql, qr] 求和：完全落入取区间和；同值段按重叠长度直接算，否则递归两侧
ll query(int node, int lo, int hi, int ql, int qr) {
    if (ql <= lo && hi <= qr) return tsum[node];
    if (tmax[node] == tmin[node]) {
        // 部分重叠的同值段：孩子可能没同步，不能下探，直接按重叠长度算
        int overlap = min(hi, qr) - max(lo, ql) + 1;
        return tmax[node] * overlap;
    }
    int mid = (lo + hi) >> 1;
    ll total = 0;
    if (ql <= mid) total = query(node << 1, lo, mid, ql, qr);
    if (qr > mid) total += query(node << 1 | 1, mid + 1, hi, ql, qr);
    return total;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &delta[i]);
    build(1, 1, n);

    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int x, l, r;
        scanf("%d %d %d", &x, &l, &r);
        if (x == 1) {
            // 询问 l..r 的开心值总和
            printf("%lld\n", query(1, 1, n, l, r));
        } else {
            // l..r 每个国家的喜欢度开方取整
            apply_sqrt(1, 1, n, l, r);
        }
    }
    return 0;
}

复杂度

时间复杂度：建树 $O(n)$ ；每次询问 $O(\log n)$ 。区间开方中，落在操作区间边界上的节点共 $O(\log n)$ 个，其余被访问的节点都在"区间内仍有值 $> 1$ "的下探路径上，且必然终止于一个值真正被开方的叶子；单个叶子至多变化 5 次，故全部操作的值变化总次数 $\leqslant 5n$ ，每次变化花费 $O(\log n)$ 。合计 $O((n + m) \log n)$ ，常数约为 5，与 C++ 正解同阶。
空间复杂度：线段树 $4n$ 个节点、每节点 3 个整数，加上输出列表共 $O(n + m)$ 。

总结

区间加、区间求和有线段树懒标记这套标准工具，但非线性修改（开方）没有统一标记可打——这不是绝路，因为题目恰好给了一个"操作会自己耗尽"的性质：任何值开方 5 次以内就收敛到 0/1，后续操作全是无效功。解法就是把这份有限性变成均摊界：线段树节点额外维护最大/最小值，用 $\max \leqslant 1$ 整段跳过、 $\max = \min$ 整段改写，让每次节点改写都对应值的真实变化，总变化次数 $\leqslant 5n$ 。

实现上要特别留意"整段改写后孩子陈旧"的同步问题：查询对同值段直接按重叠长度计算，更新下探前先 push_equal 下推，二者配合才维持住"读到的节点值总是真实的"这一不变式。