P1531 I Hate It · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1531，日期见页头。两边不一致时信原站。

题目背景

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

题目描述

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

输入格式

第一行，有两个正整数 n 和 m（0 < n ≤ 2 × 10⁵，0 < m ≤ 2 × 10⁵），分别代表学生的数目和操作的数目。学生 ID 编号分别从 1 编到 n。

第二行包含 n 个整数，代表这 n 个学生的初始成绩，其中第 i 个数代表 ID 为 i 的学生的成绩，保证学生的成绩为 1 ~ 10⁹ 之间的正整数。

接下来有 m 行。每一行有一个字符 c（只取 Q 或 U），和两个正整数 a、b。

当 c 为 Q 的时候，表示这是一条询问操作，它询问 ID 从 a 到 b（包括 a、b）的学生当中，成绩最高的是多少；
当 c 为 U 的时候，表示这是一条更新操作， ★ 如果当前 a 学生的成绩低于 b，则把 ID 为 a 的学生的成绩更改为 b，否则不改动。

输出格式

对于每一次询问操作输出一行一个整数，表示最高成绩。

输入输出样例

输入

输出

初始成绩 1 2 3 4 5。Q 1 5 ⇒ 5；U 3 6（3 < 6，改）⇒ 1 2 6 4 5； Q 3 4 ⇒ 6；Q 4 5 ⇒ 5；U 2 9（2 < 9，改）⇒ 1 9 6 4 5；Q 1 5 ⇒ 9。

1⚠ 先说读题：这道题的第一个坑不在线段树里

p1531Set.cpp✗ 把 U 当成无条件赋值 —— 而官方样例一个字都不会变

// P1531 ✗ 错法：把 `U a b` 当成**无条件赋值**
//
// ★★ 这是这道题最典型的第一版 —— 而它**和线段树一点关系都没有，纯粹是读题**。
//   题面原话：「如果当前 a 学生的成绩**低于** b，则把 ID 为 a 的学生的成绩更改为 b，
//   **否则不改动**。」
//
// ⚠⚠ 而**官方样例挡不住它**：样例里两次更新是 `U 3 6`（3 → 6）和 `U 2 9`（2 → 9），
//   两次都是往大了改 ⇒ 无条件赋值和「低于才改」**给出一模一样的输出**。
//   ⇒ 又一个「[样例是一测就死的过滤器](/sol/p1223/)」的反例。
//
// ★ 触发条件写得出来：**存在一次 `U a b` 满足 a 的当前成绩 > b**。
//   顺手写的生成器（成绩和 b 都在同一个值域里随机）几乎每轮都会撞上 ⇒ 对拍一抓一个准。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int mx[MAXN * 4];
int a[MAXN];
int n, m;

inline void pushup(int o) { mx[o] = max(mx[o * 2], mx[o * 2 + 1]); }

void build(int o, int l, int r) {
    if (l == r) { mx[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

void assign(int o, int l, int r, int p, int v) {
    if (l == r) { mx[o] = v; return; }          // ⚠ 就是这一句：没有比较，直接盖掉
    int mid = (l + r) / 2;
    if (p <= mid) assign(o * 2, l, mid, p, v);
    else assign(o * 2 + 1, mid + 1, r, p, v);
    pushup(o);
}

int query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mx[o];
    int mid = (l + r) / 2;
    int best = INT_MIN;
    if (ql <= mid) best = max(best, query(o * 2, l, mid, ql, qr));
    if (qr > mid) best = max(best, query(o * 2 + 1, mid + 1, r, ql, qr));
    return best;
}

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'Q') { out += to_string(query(1, 1, n, x, y)); out += '\n'; }
        else assign(1, 1, n, x, y);
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 「U a b」不是赋值，而官方样例正好挡不住

题面写得很清楚：「如果当前 a 学生的成绩低于 b，则把成绩改成 b，否则不改动」—— 也就是 a[x] = max(a[x], y)，不是 a[x] = y。

⚠⚠ 而样例里那两次更新是 U 3 6（3 → 6）和 U 2 9（2 → 9），两次都是往大了改 ⇒ 无条件赋值和「低于才改」在这组样例上给出完全一样的输出（你可以点上面那个「运行 ▶」自己看）。 ⇒ 又一个「样例是一测就死的过滤器」的反例。

★ 它的触发条件写得出来：存在一次 U a b 满足 a 当前的成绩 > b。而这是两层的（p1531Count.cpp 每档 300 轮）：

档位	存在「b < 当前成绩」	真被抓	比
0 顺手写的（值域 20）	271	109	2.5 倍
1 照题面值域 `10⁹`	277	107	2.6 倍
★ 2 `U` 的 `b` 恒变大（就是样例那个形状）	0	★ 精确的 0	——
3 查询恒为 `[1, n]`	277	77	3.6 倍

★★ 第 ② 层为什么比第 ① 层小这么多：U 把成绩改小了还不够， 那个位置还得真的是某次询问区间里的最大值，答案才会变。 ⇒ 「触发条件 ≈ 抓获率」有时对、有时差 60 倍，只能量不能推。

2第 ① 版：每次询问扫一遍 —— ★ 而这道题一分都不给

p1531Brute.cpp第 ① 版：查询 O(区间长) —— 参照物，但拿不到分

★ 「暴力值多少分」是「暴力 × 那道题分档」的属性

隔壁那道 P3372 的题面把 15% / 35% 两档写得明明白白，暴力白捡 35 分。 这道题一档都没有 —— 题面只有一句 0 < n, m ≤ 2 × 10⁵。

顶格实测（A 机 · WSL2 · 2026-09-01 · 独占 · 进程内 steady_clock）：暴力 3193 毫秒（碰了 66.4 亿个格子），时限 1 秒 ⇒ 0 分。

⇒ 同一个「每次重扫一遍」，在第 37 章 P1168 上稳拿 40 分、在 P1801 上一分不给、在 P3372 上值 35 分。先去数据范围里找分档，再决定写不写它。

3★ 正解：这正是自测清单里那条「只需改哪两处」的考场版

p1531.cpp正解：线段树（单点改 + 区间最大值）—— 比章节那份还短

// P1531 正解 —— 线段树（单点改 + 区间最大值）
//
// ★★ 这道题正是[第 39 章](/ch/39-segment-tree/)自测清单里那条
//   「把这一章的代码改成『区间加 + 区间最大值』，并说清只需要改哪两处」的**考场版**，
//   而且比那条还省一处 —— 这道题只有**单点**改：
//
//     ① pushup：sm[o] = sm[2o] + sm[2o+1]   →   mx[o] = max(mx[2o], mx[2o+1])
//     ② apply 里那句「乘区间长度」**整个消失了**
//        （长度只对「和」有意义：一段每人加 x，和涨 x·len；而最大值涨 x，和 len 无关）
//     ★ ③ 而这道题连懒标记都不用 —— 单点改就是「递归到叶子、改一格、一路 pushup 回来」。
//
// ⇒ 所以这一版比章节那份**短**：没有 lz、没有 pushdown、没有 len。
//
// ⚠ 读题：`U a b` 是「a 的成绩**低于** b 才改成 b」，不是无条件赋值（见 p1531Set.cpp）。
// ⚠ 读入：`c` 是字符，和两个整数混着读 —— cin >> char 会自己跳空白，scanf 要写 " %c"。
//
// 复杂度：建树 O(n)，每次操作 O(log n)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int mx[MAXN * 4];                              // ⚠ 仍然是 4n
int a[MAXN];
int n, m;

inline void pushup(int o) { mx[o] = max(mx[o * 2], mx[o * 2 + 1]); }

void build(int o, int l, int r) {
    if (l == r) { mx[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 单点改：把第 p 个数抬到至少 v（题面那句「低于才改」） */
void raise(int o, int l, int r, int p, int v) {
    if (l == r) { if (mx[o] < v) mx[o] = v; return; }
    int mid = (l + r) / 2;
    if (p <= mid) raise(o * 2, l, mid, p, v);
    else raise(o * 2 + 1, mid + 1, r, p, v);
    pushup(o);
}

int query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mx[o];
    int mid = (l + r) / 2;
    int best = INT_MIN;
    if (ql <= mid) best = max(best, query(o * 2, l, mid, ql, qr));
    if (qr > mid) best = max(best, query(o * 2 + 1, mid + 1, r, ql, qr));
    return best;
}

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'Q') { out += to_string(query(1, 1, n, x, y)); out += '\n'; }
        else raise(1, 1, n, x, y);
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 把「区间和」改成「区间最大值」，到底改了哪几处

第 39 章自测清单里那条是「改成区间加 + 区间最大值，说清只改哪两处」。这道题更省一处，因为它只有单点改：

改的地方	区间和版	这一版
① `pushup`	`sm[o] = sm[2o] + sm[2o+1]`	`mx[o] = max(mx[2o], mx[2o+1])`
② `apply` 里那句「乘区间长度」	`sm[o] += x * len`	★ 整个消失了
★ ③ 懒标记	必须有	★ 也不用了

★ 第 ② 行的道理一句话：长度只对「和」有意义 —— 一段里每人加 x，和涨 x · len，而最大值只涨 x，和 len 没关系。 ★ 第 ③ 行：单点改就是「递归到叶子、改一格、一路 pushup 回来」，没有「欠着的账」。

⇒ 所以这一版比章节那份还短：没有 lz、没有 pushdown、没有 len。 ⚠ 但 4n 还是要开（P3372 那一节算过：最先撑破 2n 的是 n = 6）。

4★★★ 第 39 章末尾那句「最大值没有减法」，在这道题上被题面绕开了

★ 先把那句话补上主语

第 39 章第 13 步的结论是：

树状数组靠 sum(r) − sum(l−1) 拿区间和，而最大值没有减法 —— 第 38 章那句「可以修改的前缀和」，前缀这两个字是有代价的。

这句话是对的，但它省略了一个主语：做不了的是「任意的单点改 + 区间最值」。

★★★ 而这道题的更新是「低于才改」⇒ 每个位置只增不减。一旦只增，c[i] = max(它管的那一段) 这个值永远不需要变小 —— 修改时沿着 i += i & -i 一路 max 上去就够了。 ⇒ 题面那半句话是一张许可证：它把「没有减法」这个障碍整个绕开了。

p1531Bit.cpp★ 第 ③ 版：树状数组求区间最大值 —— 查询 O(log²n)

// P1531 第 ③ 版：**树状数组也能求区间最大值** —— 而它成立，靠的正是题面那半句话
//
// ============ ★★★ 先看看它凭什么和第 39 章末尾那句话不矛盾 ============
//
//   [第 39 章第 13 步](/ch/39-segment-tree/)的结论是：
//   「树状数组靠 `sum(r) − sum(l−1)` 拿区间和，而**最大值没有减法** ⇒ 它做不了区间最值。」
//   **这句话是对的**，可它省略了一个主语 —— 做不了的是「**任意的**单点改 + 区间最值」。
//
//   ★ 而这道题的更新是：「如果当前成绩**低于** b，才改成 b」⇒ **每个位置只增不减**。
//     一旦「只增」，`c[i] = max(该管的那一段)` 这个值就**永远不需要变小** ——
//     修改时沿着 `i += i & -i` 一路 `max` 上去就行，不用重算。
//   ⇒ ★★ **题面那半句话是一张许可证**：它把「没有减法」这个障碍绕开了。
//   ⚠ 而查询仍然比线段树贵一个 log：区间最值要 O(log²n)（见下面 rangeMax 的循环）。
//
//   ⇒ 自检见 p1531Gen.cpp 的档 3：**造一档允许成绩变小的数据**（违反题面），
//     这一版当场就错，而线段树版一点事都没有。
//     ⇒ 同一个动作干了两件事：证明这段代码是活的 ＋ 称出那半句话是**命门**。
//
// ============ 区间最值怎么查（O(log²n)）============
//
//   c[i] 管的是 (i − lowbit(i), i] 这一段。从 r 往左走：
//     · 如果 c[r] 管的那一整段还在 [l, r] 里面（r − lowbit(r) ≥ l − 1），就吃掉 c[r]，r −= lowbit(r)；
//     · 否则只能一格一格退：吃掉 a[r]，r−−。
//   每一步要么砍掉一个 lowbit、要么退一格，总共 O(log²n)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int a[MAXN], c[MAXN];
int n, m;

/** 只增的单点改：a[i] 抬到至少 v */
inline void raise(int i, int v) {
    if (a[i] >= v) return;                      // ★ 题面那句「低于才改」
    a[i] = v;
    for (int j = i; j <= n; j += j & -j) if (c[j] < v) c[j] = v;
}

inline int rangeMax(int l, int r) {
    int res = 0;                                // 成绩都是正数，0 当下界安全
    while (r >= l) {
        if (r - (r & -r) >= l - 1) { res = max(res, c[r]); r -= r & -r; }
        else { res = max(res, a[r]); r--; }
    }
    return res;
}

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) { int v; cin >> v; raise(i, v); }

    string out;
    for (int q = 0; q < m; q++) {
        char ch;
        int x, y;
        cin >> ch >> x >> y;
        if (ch == 'Q') { out += to_string(rangeMax(x, y)); out += '\n'; }
        else raise(x, y);
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 而这句「靠的是那半句话」不能只是说说 —— 它配了自检

「p1531Bit 在 300 轮里一次都不错」这种精确的 0，本书的规矩是报 0 之前先拿一个已知错的东西验一遍。这里的自检办法很省事：把题面那半句话去掉再跑一遍。

p1531BitSet.cpp 和上面那一版只差一处（raise 换成无条件的 assign），参照物是 p1531Set.cpp（线段树 + 同一条改过的规则，在这条规则下它是正确的）：

档位	树状数组那条路塌掉的轮数
0 顺手写的	85 / 300
1 照题面值域	81 / 300
★ 2 `U` 恒变大	★ 0 / 300
3 查询恒为 `[1,n]`	77 / 300

★★★ 第 ③ 行那个 0 尤其值钱：那一档里「无条件赋值」和「低于才改」本来就是同一条规则 （因为 b 恒大于当前成绩）⇒ 它塌不了。 ⇒ 同一个档位同时把「错法」和「自检」都打成 0，而两个 0 是同一个原因。

⇒ 于是这个动作照例干了两件事（和 P1439 那次一样）： ① 证明那段查询代码是活的；② 称出「低于才改」是命门 —— 少了它，这条路根本不成立。

p1531BitSet.cpp⚠ 自检用：树状数组＋「无条件赋值」这条改过的规则 —— 它当场就塌

5★★ 两把尺子第三次打架 —— 而这次复杂度更差的那个赢了

p1531Count.cpp本页所有数字的出处

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

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

// P1531 的度量程序：./p1531Count csv        （本页的数字都出自它）
//
//   trig  : ★★★ 「把 U 当成无条件赋值」那个错法的**两层触发条件**：
//           ① 这一轮里存在一次 `U a b` 满足 a 当前的成绩 > b   ② 它真被抓
//           ⇒ 两层之间差多少，是量出来的，不是推出来的。
//   ms    : 顶格 n = m = 2×10⁵ 上暴力 / 线段树 / 树状数组的毫秒。
//   steps : ★★ 换一把机器无关的尺子 —— 一次区间最值查询平均碰几个节点。
//           线段树是 O(log n)，树状数组那条路是 O(log²n) ⇒ 这把尺子看得见，秒表不一定。
//   brute : 暴力在顶格上碰了多少个格子（这道题**没有分档** ⇒ 它一分都拿不到）。
//
// ⚠ 秒表一律用 steady_clock 在进程内量（[第 35 章 P2866](/sol/p2866/) 那一跤）。
// ⚠ 这里**复刻**了 p1531Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

struct Op { char c; int x, y; };
struct Data { int n, m; vector<int> a; vector<Op> ops; };

static Data gen(unsigned seed, int mode) {
    mt19937 rng(seed * 1000003u + 20260901u);
    Data d;
    int n, m;
    if (mode == 4 || mode == 5) { n = 200000; m = 200000; }
    else { n = 6 + (int)(rng() % 7u); m = 6 + (int)(rng() % 7u); }
    int hi = (mode == 0) ? 20 : 1000000000;
    d.n = n; d.m = m; d.a.assign(n + 1, 0);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) { int v = 1 + (int)(rng() % (unsigned)hi); a[i] = v; d.a[i] = v; }
    for (int q = 0; q < m; q++) {
        int x = 1 + (int)(rng() % (unsigned)n);
        int y = 1 + (int)(rng() % (unsigned)n);
        bool isQ;
        if (mode == 5) isQ = (q % 10 != 0);
        else isQ = (rng() % 2u) == 0;
        if (isQ) {
            if (x > y) swap(x, y);
            if (mode == 3) { x = 1; y = n; }
            d.ops.push_back({'Q', x, y});
        } else {
            int v;
            if (mode == 2) {
                long long room = (long long)hi - a[x];
                if (room <= 0) v = a[x];
                else v = a[x] + 1 + (int)(rng() % (unsigned)room);
            } else v = 1 + (int)(rng() % (unsigned)hi);
            if (a[x] < v) a[x] = v;
            d.ops.push_back({'U', x, v});
        }
    }
    return d;
}

/** 第一层：这一轮里存在「U 的 b 小于当前成绩」吗（那正是无条件赋值会出事的地方） */
static bool hasLower(const Data& d) {
    vector<int> a(d.a);
    for (const Op& o : d.ops) {
        if (o.c == 'U') { if (a[o.x] > o.y) return true; if (a[o.x] < o.y) a[o.x] = o.y; }
    }
    return false;
}

static vector<int> bruteRun(const Data& d, long long& steps) {
    vector<int> a(d.a), out;
    for (const Op& o : d.ops) {
        if (o.c == 'Q') { int b = 0; for (int i = o.x; i <= o.y; i++) { b = max(b, a[i]); steps++; } out.push_back(b); }
        else if (a[o.x] < o.y) a[o.x] = o.y;
    }
    return out;
}

/** 线段树（正解语义） */
static int SN; static vector<int> mx;
static void sBuild(int o, int l, int r, const vector<int>& a) {
    if (l == r) { mx[o] = a[l]; return; }
    int mid = (l + r) / 2; sBuild(o * 2, l, mid, a); sBuild(o * 2 + 1, mid + 1, r, a);
    mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}
static void sRaise(int o, int l, int r, int p, int v) {
    if (l == r) { if (mx[o] < v) mx[o] = v; return; }
    int mid = (l + r) / 2;
    if (p <= mid) sRaise(o * 2, l, mid, p, v); else sRaise(o * 2 + 1, mid + 1, r, p, v);
    mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}
static long long qSteps;
static int sQry(int o, int l, int r, int ql, int qr) {
    qSteps++;
    if (ql <= l && r <= qr) return mx[o];
    int mid = (l + r) / 2, best = 0;
    if (ql <= mid) best = max(best, sQry(o * 2, l, mid, ql, qr));
    if (qr > mid) best = max(best, sQry(o * 2 + 1, mid + 1, r, ql, qr));
    return best;
}
static vector<int> segRun(const Data& d, long long& steps) {
    SN = d.n; mx.assign((size_t)d.n * 4 + 4, 0); sBuild(1, 1, d.n, d.a);
    qSteps = 0;
    vector<int> out;
    for (const Op& o : d.ops) {
        if (o.c == 'Q') out.push_back(sQry(1, 1, d.n, o.x, o.y));
        else sRaise(1, 1, d.n, o.x, o.y);
    }
    steps = qSteps;
    return out;
}

/** 树状数组求区间最值（只增） */
static vector<int> bitRun(const Data& d, long long& steps) {
    int n = d.n;
    vector<int> a(n + 1, 0), c(n + 1, 0);
    auto raise = [&](int i, int v) {
        if (a[i] >= v) return;
        a[i] = v;
        for (int j = i; j <= n; j += j & -j) if (c[j] < v) c[j] = v;
    };
    for (int i = 1; i <= n; i++) raise(i, d.a[i]);
    long long st = 0;
    auto rmax = [&](int l, int r) {
        int res = 0;
        while (r >= l) {
            st++;
            if (r - (r & -r) >= l - 1) { res = max(res, c[r]); r -= r & -r; }
            else { res = max(res, a[r]); r--; }
        }
        return res;
    };
    vector<int> out;
    for (const Op& o : d.ops) {
        if (o.c == 'Q') out.push_back(rmax(o.x, o.y));
        else raise(o.x, o.y);
    }
    steps = st;
    return out;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 「无条件赋值」那个错法的两层触发条件 */
    int trig[4] = {0, 0, 0, 0}, caught[4] = {0, 0, 0, 0};
    for (int mode = 0; mode <= 3; mode++) {
        for (int s = 1; s <= 300; s++) {
            Data d = gen(s, mode);
            if (hasLower(d)) trig[mode]++;
            // 无条件赋值的语义，直接模拟
            vector<int> a(d.a), out1, out2;
            for (const Op& o : d.ops) {
                if (o.c == 'Q') { int b = 0; for (int i = o.x; i <= o.y; i++) b = max(b, a[i]); out1.push_back(b); }
                else a[o.x] = o.y;
            }
            long long st;
            out2 = bruteRun(d, st);
            if (out1 != out2) caught[mode]++;
        }
    }

    /* ② 顶格秒表 + 查询步数 */
    Data top = gen(1, 4);
    long long stB = 0, stS = 0, stT = 0;
    auto t0 = steady_clock::now(); vector<int> ob = bruteRun(top, stB);
    double msB = duration<double, milli>(steady_clock::now() - t0).count();
    t0 = steady_clock::now(); vector<int> os = segRun(top, stS);
    double msS = duration<double, milli>(steady_clock::now() - t0).count();
    t0 = steady_clock::now(); vector<int> ot = bitRun(top, stT);
    double msT = duration<double, milli>(steady_clock::now() - t0).count();
    bool same = (ob == os && os == ot);
    int qcnt = 0;
    for (const Op& o : top.ops) if (o.c == 'Q') qcnt++;

    if (csv) {
        for (int i = 0; i < 4; i++) printf("trig%d,%d\ncaught%d,%d\n", i, trig[i], i, caught[i]);
        printf("msB,%.0f\nmsS,%.0f\nmsT,%.0f\n", msB, msS, msT);
        printf("stB,%lld\nstS,%lld\nstT,%lld\n", stB, stS, stT);
        printf("qcnt,%d\n", qcnt);
        printf("perQs,%.1f\nperQt,%.1f\n", (double)stS / qcnt, (double)stT / qcnt);
        printf("same,%d\n", same ? 1 : 0);
        printf("ratioSteps,%.2f\nratioMs,%.2f\n", (double)stT / stS, msT / max(0.001, msS));
        return 0;
    }

    printf("① 「把 U 当成无条件赋值」那个错法的两层触发条件（每档 300 轮）：\n\n");
    const char* NAME[4] = {"0 顺手（值域 20）", "1 照题面值域 10⁹", "2 ★ U 恒变大（样例那个形状）", "3 查询恒为 [1,n]"};
    for (int i = 0; i < 4; i++)
        printf("   %-28s 存在「b < 当前成绩」%3d 轮 ｜ 真被抓 %3d 轮\n", NAME[i], trig[i], caught[i]);

    printf("\n② 顶格 n = m = 2×10⁵（%d 次查询）：\n", qcnt);
    printf("   暴力       %6.0f ms（碰了 %lld 个格子）\n", msB, stB);
    printf("   线段树     %6.0f ms（查询共走 %lld 步，每次 %.1f）\n", msS, stS, (double)stS / qcnt);
    printf("   树状数组   %6.0f ms（查询共走 %lld 步，每次 %.1f）⇒ 步数是线段树的 %.2f 倍\n",
           msT, stT, (double)stT / qcnt, (double)stT / stS);
    printf("   三者答案一致：%s\n", same ? "是" : "★ 不一致！");
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

★★★ 步数多 1.59 倍，秒表快 2.5 倍

顶格实测（n = m = 2 × 10⁵，其中 99 891 次查询；A 机 · WSL2 · 2026-09-01 · 独占 · 进程内 steady_clock，不含读入）：

做法	查询复杂度	每次查询走几步	秒表
暴力	O(区间长)	—— （共碰 66.4 亿格）	3193 ms ⇒ TLE
线段树	★ O(log n)	47.1	37 ms
树状数组	⚠ O(log²n)	74.6（多 1.59 倍）	★ 15 ms（快 2.5 倍）

★★★ 复杂度更差的那一版，秒表上快了 2.5 倍。 差在哪儿说得清：树状数组那条路是一个平的 while 循环（下标连续、没有函数调用、没有分支预测失败的递归），线段树是递归（每层一次函数调用、一次区间比较）。

⇒ 这是第 29 章 P2853、P1074 那条的第 N 次现场，而且这次方向是反的：以前是「次数一样、秒表差很多」，这次是「次数更多、秒表反而更快」。 ⇒ 次数和秒表量的从来不是同一件事，两个都要报。

6★ 那么，哪一版就已经能过了

第 ② 版（线段树）就能过，而且余量 27 倍

版本	顶格耗时	交上去
① 暴力	3193 ms	0 分（这道题没有分档）
★ ② 线段树	37 ms（时限 1 秒）	★ AC，余量 27 倍
★ ③ 树状数组求区间最值	15 ms	★ AC，余量 66 倍

⇒ 该写哪一个？ 考场上写线段树 —— 它短、好想、而且不依赖「只增不减」这个前提。第 ③ 版的价值不在快，在于它把第 39 章那句话的主语给量出来了。

⚠ 最后一条和算法无关的：c 是字符，和两个整数混着读。 cin >> char 会自己跳空白，而 scanf 必须写成 scanf(" %c", &c)（前面那个空格不能少）。

洛谷 P1531 I Hate It

0题目原文（本地存了一份）

输入

输出

1⚠ 先说读题：这道题的第一个坑不在线段树里

2第 ① 版：每次询问扫一遍 —— ★ 而这道题一分都不给

3★ 正解：这正是自测清单里那条「只需改哪两处」的考场版

4★★★ 第 39 章末尾那句「最大值没有减法」，在这道题上被题面绕开了

5★★ 两把尺子第三次打架 —— 而这次复杂度更差的那个赢了

6★ 那么，哪一版就已经能过了