P1198 [JSOI2008] 最大数 · 习题解析｜信息学奥赛算法练功房

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

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

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

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

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1. 查询操作。

语法：Q L

功能：查询当前数列中末尾 L 个数中的最大的数，并输出这个数的值。

限制：L 不超过当前数列的长度（L > 0）。

2. 插入操作。

语法：A n

功能：将 n 加上 t，其中 t 是最近一次查询操作的答案（如果还未执行过查询操作，则 t = 0），并将所得结果对一个固定的常数 D 取模，将所得答案插入到数列的末尾。

限制：n 是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入格式

第一行两个整数，M 和 D，其中 M 表示操作的个数，D 如上文中所述。

接下来的 M 行，每行一个字符串，描述一个具体的操作。语法如上文所述。

输出格式

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

数据范围

对于全部的测试点，保证 1 ≤ M ≤ 2 × 10⁵，1 ≤ D ≤ 2 × 10⁹。

输入输出样例

输入

输出

96
93
96

D = 100。① A 96 ⇒ 插入 (96 + 0) mod 100 = 96，数列 [96]； ② Q 1 ⇒ 末尾 1 个数的最大值 96，于是 t = 96； ③ A 97 ⇒ 插入 (97 + 96) mod 100 = 93，数列 [96, 93]； ④ Q 1 ⇒ 末尾 1 个 ⇒ 93（t 变成 93）；⑤ Q 2 ⇒ 末尾 2 个 ⇒ 96。

1★★ 先读懂「强制在线」这四个字 —— 它不是吓唬人的

★ 判据：你能不能把输入先读完再动手

A n 插进去的不是 n，是 (n + t) mod D，而 t 是最近一次查询的答案。

⇒ 不先算出前面的答案，就不知道后面要插什么数。第 38 章 P1972 那一招（把询问全读进来、按右端点排序、离线回答）在这道题上从根上被堵死了。

★ 而这不是修辞 —— 它是能量的。p1198Count.cpp 数了一下「插进去的值真的被 t 改动过」的比例，四个档位都是 64% ~ 65%：

档位	插入值被 `t` 改动的比例
0 顺手写的（`D = 100`）	65%
1 `n` 可为负	64%
2 `D` 顶格 `2 × 10⁹`	65%
3 照着溢出那条线造	65%

⇒ 三分之二的插入值都依赖上一次的答案。 这道题只能一边读一边算。

2第 ① 版：原样存下来，每次往前扫 L 个

p1198Brute.cpp第 ① 版：查询 O(L) —— 参照物

// P1198 第 ① 版：把数列原样存下来，每次询问从末尾往前扫 L 个
//
// ★ 它是参照物。复杂度 O(ML)，顶格 M = 2×10⁵ 且每次都问整段 ⇒ 4×10¹⁰，过不去。
// ⚠ 但这道题的两个坑**和线段树无关，两个都在这一版里就要处理对**：
//   ① `A n` 里的 n **可能是负数**，而 (n + t) % D 在 C++ 里**可以是负的** ⇒ 要补一次 +D；
//   ② n「在长整范围内」⇒ **先取模再相加**，否则 n + t 自己就能撑破 long long。

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

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

    long long M, D;
    if (!(cin >> M >> D)) return 0;
    vector<long long> a;
    long long t = 0;                            // 最近一次查询的答案
    string out;
    for (long long i = 0; i < M; i++) {
        char op;
        long long x;
        cin >> op >> x;
        if (op == 'A') {
            long long v = ((x % D) + (t % D)) % D;   // ★ 先各自取模再相加（防溢出）
            if (v < 0) v += D;                       // ★ C++ 的 % 对负数给负数
            a.push_back(v);
        } else {
            long long best = LLONG_MIN;
            for (long long j = (long long)a.size() - x; j < (long long)a.size(); j++)
                best = max(best, a[j]);
            t = best;
            out += to_string(best);
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

顶格 M = 2 × 10⁵（实测 10 万次查询）它碰了 25.06 亿个格子、1208 毫秒，时限 1 秒 ⇒ 过不去。而这道题也没有分档 ⇒ 一分不给。

3★ 正解：一棵「预先开好、慢慢填」的线段树

p1198.cpp正解：按 [1, M] 建空树，插入 = 单点改，查询 = 区间最值

// P1198 正解 —— 线段树（只往末尾插入 + 区间最大值）
//
// ============ ★★ 这道题为什么必须「在线」============
//
//   `A n` 插进去的不是 n，是 (n + t) mod D，**而 t 是最近一次查询的答案**。
//   ⇒ 你不读完前面的答案，就**不知道后面要插什么数** ——
//     「把询问全读进来、排个序、离线处理」这条路（[第 38 章 P1972](/sol/p1972/) 那招）
//     在这里**被题面从根上堵死了**。
//   ⇒ ★ 这就是「强制在线」四个字的全部含义：它不是一句吓唬人的话，是一条**结构性**的限制。
//
// ============ 结构：一棵「预先开好、慢慢填」的线段树 ============
//
//   插入只发生在**末尾**，而且总共不超过 M 次
//   ⇒ 直接按 [1, M] 建一棵空树（初值取一个比任何合法值都小的下界），
//     插入 = 单点改第 len 个位置，查询 = 区间最值 [len − L + 1, len]。
//   ⇒ 用不着「动态开点」，也用不着懒标记 —— 和 [P1531](/sol/p1531/) 是同一副骨架。
//
// ⚠ 两个和线段树无关的坑（见 p1198Mod.cpp）：负数取模、以及先取模再相加。
//
// 复杂度：每次操作 O(log M)。

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

const int MAXM = 200005;
long long mx[MAXM * 4];
int M;

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

void setAt(int o, int l, int r, int p, long long v) {
    if (l == r) { mx[o] = v; return; }
    int mid = (l + r) / 2;
    if (p <= mid) setAt(o * 2, l, mid, p, v);
    else setAt(o * 2 + 1, mid + 1, r, p, v);
    mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}

long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mx[o];
    int mid = (l + r) / 2;
    long long best = LLONG_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);

    long long mm, D;
    if (!(cin >> mm >> D)) return 0;
    M = (int)mm;
    build(1, 1, max(M, 1));

    int len = 0;
    long long t = 0;
    string out;
    for (int i = 0; i < M; i++) {
        char op;
        long long x;
        cin >> op >> x;
        if (op == 'A') {
            long long v = ((x % D) + (t % D)) % D;
            if (v < 0) v += D;
            setAt(1, 1, max(M, 1), ++len, v);
        } else {
            long long best = query(1, 1, max(M, 1), len - (int)x + 1, len);
            t = best;
            out += to_string(best);
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 这道题连「动态开点」都不用

插入只发生在末尾，而且总共不超过 M 次 ⇒ 直接按 [1, M] 建一棵空树（初值取一个比任何合法值都小的下界），插入就是「单点改第 len 个位置」，查询就是「区间最值 [len − L + 1, len]」。

⇒ 骨架和 P1531 一模一样：没有懒标记，没有 pushdown，没有「乘区间长度」。 ★ 这一章五道题里有三道是这副骨架 —— 换的只是 pushup 那一行和「谁来触发修改」。

4⚠⚠ 两个和线段树毫无关系的坑 —— 而官方样例两个都挡不住

p1198Mod.cpp✗ 坑一：忘了 C++ 的 % 对负数给负数

p1198Add.cpp✗ 坑二：先把 n 和 t 加起来再取模 —— 一条极窄的线

★★★ 两个坑的触发线，一个宽一个极窄 —— 而这决定了对拍造不造得出来

坑一：负数取模。 题面写着「n 是整数（可能为负数）」。数学上的 mod 落在 [0, D)，而 C++ 的 % 是「向零取整」的余数 ⇒ (−7) % 100 在 C++ 里是 −7，不是 93。

坑二：先加再取模。 n「在长整范围内」⇒ 可以到 9.22 × 10¹⁸，而 t < D ≤ 2 × 10⁹ ⇒ n + t 能撑破 long long。

档位（每档 300 轮）	余数为负的轮数	坑一被抓	`n + t` 会溢出的轮数	坑二被抓
0 顺手写的（`n` 全正）	0	★ 精确的 0	0	0
1 `n` 可为负	257	199	0	0
2 `D` 顶格、`n ∈ ±10¹⁸`	255	212	0	0
★ 3 照着溢出那条线造	0	0	184	★ 118

★★★ 第 ④ 列那一串 0 是这一节的重点：坑二的触发线极窄 —— 要 n > 2⁶³ − 1 − t，也就是 n 必须落在最上面那 t 个整数里。照题面在整个长整范围里随机，撞上的概率约 D / 2⁶⁴ ≈ 10⁻¹⁰ ⇒ 加多少轮都没用，只能照着那条线造（p1198Gen.cpp 档 3 直接从 2⁶³ − 1 往下取）。 ⇒ 这正是「抓不到时别加轮数，去想那条线在哪儿、然后照着它造」。

⚠⚠ 而官方样例两个坑都挡不住：样例里 n 是 96 和 97， 既不是负数、也不接近长整上界 ⇒ 三个版本打出一模一样的 96 / 93 / 96 （上面三个「运行 ▶」都可以自己点一下）。

5★★ 第 ③ 版：单调栈 + 二分 —— 一条和线段树一行不共享的路

★ 这道题的两个操作有一个很特别的组合

只在末尾插入，而且只问后缀的最大值 —— 这正好是第 35 章那套单调栈的形状。

维护一个「下标递增、值严格递减」的栈：新数进来时把栈尾所有 ≤ 它的弹掉，再压进去。 ★ 于是有一条能证的性质：被弹掉的数一定被某个下标更大的数盖住了 ⇒ 问后缀 [x, len] 的最大值，只要找栈里第一个下标 ≥ x 的元素，它的值就是答案。 ⇒ 栈里下标有序 ⇒ 二分。插入均摊 O(1)，查询 O(log)。

p1198Stack.cpp★ 第 ③ 版：单调栈 + 二分 —— 比线段树短一半，顶格快 6.5 倍

// P1198 第 ③ 版：**单调栈 + 二分** —— 一条和线段树一行代码都不共享的路
//
// ============ ★★★ 为什么这道题能这么做 ============
//
//   这道题的两个操作有一个很特别的组合：**只在末尾插入**，而且**只问后缀的最大值**。
//   ⇒ 维护一个「值严格递减」的下标栈（[第 35 章](/ch/35-monotonic/)那套）：
//     新数进来时，把栈尾所有 ≤ 它的弹掉，再压进去。
//
//   ★ 于是栈里从左到右下标递增、值递减，而且有一条能证的性质：
//     **被弹掉的那些数，一定被某个下标更大的数「盖住」了** ——
//     所以问后缀 [x, len] 的最大值，只要在栈里找**第一个下标 ≥ x 的元素**，
//     它的值就是答案（再往后的值都更小）。
//   ⇒ 栈里下标是有序的 ⇒ **二分**。插入均摊 O(1)，查询 O(log)。
//
//   ⇒ ★★ 它的价值不在快（见页面那张表，它和线段树差不多），
//     而在于它是一条**完全独立**的路：拿它和线段树对拍，
//     两边一行代码都不共享（[「验算要走一条和算法完全无关的路」](/sol/p1332/)）。
//
// ⚠ 那两个和算法无关的坑照旧：负数取模、先取模再相加。

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

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

    long long M, D;
    if (!(cin >> M >> D)) return 0;

    vector<long long> val;                      // val[i]：第 i 个插入的数（下标从 1 数）
    vector<int> stk;                            // 下标递增、值严格递减
    long long t = 0;
    string out;
    for (long long i = 0; i < M; i++) {
        char op;
        long long x;
        cin >> op >> x;
        if (op == 'A') {
            long long v = ((x % D) + (t % D)) % D;
            if (v < 0) v += D;
            val.push_back(v);
            int idx = (int)val.size();
            while (!stk.empty() && val[stk.back() - 1] <= v) stk.pop_back();
            stk.push_back(idx);
        } else {
            int len = (int)val.size();
            int lo = len - (int)x + 1;           // 要问的是 [lo, len]
            // 栈里第一个下标 ≥ lo 的元素
            int pos = (int)(lower_bound(stk.begin(), stk.end(), lo) - stk.begin());
            long long best = val[stk[pos] - 1];
            t = best;
            out += to_string(best);
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 三种做法并排（顶格 M = 2×10⁵，10 万次查询）

本机实测（A 机 · WSL2 · Linux 6.18 / 8 线程 / 7 GB，2026-09-01，独占；进程内 steady_clock，不含读入）：

做法	查询复杂度	秒表	交上去
① 暴力	O(L)	1208 ms（碰 25.06 亿格）	0 分
★ ② 线段树	O(log M)，每次 43.6 步	26 ms	★ AC，余量 38 倍
★ ③ 单调栈 + 二分	均摊 O(1) 插入 + O(log) 查询	★ 4 ms	★ AC，余量 250 倍

★★ 但第 ③ 版真正的价值不在快，在于它和线段树一行代码都不共享 —— 拿它当对拍的参照物，验的才不是「同一个假设的两种写法」（第 37 章 P2085 那一跤：堆版和归并版共享同一个前提，一起错、对拍验的是零）。四个档位 × 300 轮，三者逐字节相同。

⚠ 而它有一个线段树没有的前提：只在末尾插入、只问后缀。题目要是改成「在中间插入」或者「问任意区间」，这条路当场就没了 —— ★ 这就是第 39 章第 13 步那句「线段树能干的事多」的又一个现场。

p1198Count.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

// P1198 的度量程序：./p1198Count csv        （本页的数字都出自它）
//
//   online : ★★ 「强制在线」到底生效了没有 —— 有多少次插入的值真的被上一次的答案 t 改动过。
//            （这不是修辞：如果一次都没改动过，那这道题和离线做法就没有区别了。）
//   mod    : ★★★ 「忘了负数取模」那个错法的两层触发条件：
//            ① 这一轮里真的出现过「算出来的余数为负」 ② 它真被抓。
//   add    : ★★★ 「先加再取模」那条**极窄的线**：n 要落在最上面 t 个整数里
//            ⇒ 照题面随机撞上的概率约 D / 2⁶⁴ ≈ 10⁻¹⁰ ⇒ 那几档必然是 0。
//   ms     : 顶格 M = 2×10⁵ 上暴力 / 线段树 / 单调栈的毫秒。
//   steps  : 换一把机器无关的尺子 —— 每次查询平均碰几个节点（线段树） / 二分几步（单调栈）。
//
// ⚠ 秒表一律用 steady_clock 在进程内量。
// ⚠ 这里**复刻**了 p1198Gen.cpp 的档位逻辑（同一个 mt19937_64、同一个种子公式）。

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

struct Op { char c; long long x; };
struct Data { int M; long long D; vector<Op> ops; };

static Data gen(unsigned seed, int mode) {
    mt19937_64 rng(seed * 1000003ull + 20260901ull);
    Data d;
    int M = (mode == 4 || mode == 5) ? 200000 : 6 + (int)(rng() % 9u);
    long long D = (mode >= 2) ? 2000000000LL : 100;
    d.M = M; d.D = D;
    int len = 0;
    for (int i = 0; i < M; i++) {
        bool wantQ = (len > 0) && ((mode == 5) ? (i % 2 == 1) : ((rng() % 2ull) == 0));
        if (!wantQ) {
            long long n;
            if (mode == 0) n = 1 + (long long)(rng() % 1000ull);
            else if (mode == 1) n = (long long)(rng() % 2000001ull) - 1000000LL;
            else if (mode == 3) n = LLONG_MAX - (long long)(rng() % (unsigned long long)(2 * D));
            else {
                unsigned long long r = rng() % 2000000000000000001ull;
                n = (long long)r - 1000000000000000000LL;
            }
            d.ops.push_back({'A', n});
            len++;
        } else {
            long long L = (mode == 5) ? len : 1 + (long long)(rng() % (unsigned long long)len);
            d.ops.push_back({'Q', L});
        }
    }
    return d;
}

/** 正解语义的模拟；顺带数三件事 */
static vector<long long> simulate(const Data& d, int& changedByT, int& negMod, int& overflowed) {
    vector<long long> a, out;
    long long t = 0;
    changedByT = negMod = overflowed = 0;
    for (const Op& o : d.ops) {
        if (o.c == 'A') {
            long long raw = ((o.x % d.D) + (t % d.D)) % d.D;
            if (raw < 0) negMod++;
            long long v = raw < 0 ? raw + d.D : raw;
            long long noT = o.x % d.D; if (noT < 0) noT += d.D;
            if (v != noT) changedByT++;
            // 「先加再取模」会不会撑破 long long
            if (o.x > 0 && t > 0 && o.x > LLONG_MAX - t) overflowed++;
            a.push_back(v);
        } else {
            long long best = LLONG_MIN;
            for (size_t j = a.size() - (size_t)o.x; j < a.size(); j++) best = max(best, a[j]);
            t = best;
            out.push_back(best);
        }
    }
    return out;
}

/* 三种做法（都只量查询那一侧的步数） */
static long long qSteps;
static int SM; static vector<long long> mx;
static void build(int o, int l, int r) { mx[o] = LLONG_MIN; if (l == r) return;
    int mid = (l + r) / 2; build(o * 2, l, mid); build(o * 2 + 1, mid + 1, r); }
static void setAt(int o, int l, int r, int p, long long v) {
    if (l == r) { mx[o] = v; return; }
    int mid = (l + r) / 2;
    if (p <= mid) setAt(o * 2, l, mid, p, v); else setAt(o * 2 + 1, mid + 1, r, p, v);
    mx[o] = max(mx[o * 2], mx[o * 2 + 1]);
}
static long long qry(int o, int l, int r, int ql, int qr) {
    qSteps++;
    if (ql <= l && r <= qr) return mx[o];
    int mid = (l + r) / 2; long long b = LLONG_MIN;
    if (ql <= mid) b = max(b, qry(o * 2, l, mid, ql, qr));
    if (qr > mid) b = max(b, qry(o * 2 + 1, mid + 1, r, ql, qr));
    return b;
}
static vector<long long> segRun(const Data& d) {
    SM = max(d.M, 1); mx.assign((size_t)SM * 4 + 4, 0); build(1, 1, SM);
    qSteps = 0;
    int len = 0; long long t = 0; vector<long long> out;
    for (const Op& o : d.ops) {
        if (o.c == 'A') { long long v = ((o.x % d.D) + (t % d.D)) % d.D; if (v < 0) v += d.D; setAt(1, 1, SM, ++len, v); }
        else { long long b = qry(1, 1, SM, len - (int)o.x + 1, len); t = b; out.push_back(b); }
    }
    return out;
}
static vector<long long> stackRun(const Data& d, long long& steps) {
    vector<long long> val, out; vector<int> stk; long long t = 0; steps = 0;
    for (const Op& o : d.ops) {
        if (o.c == 'A') {
            long long v = ((o.x % d.D) + (t % d.D)) % d.D; if (v < 0) v += d.D;
            val.push_back(v); int idx = (int)val.size();
            while (!stk.empty() && val[stk.back() - 1] <= v) { stk.pop_back(); steps++; }
            stk.push_back(idx);
        } else {
            int len = (int)val.size(), lo = len - (int)o.x + 1;
            int pos = (int)(lower_bound(stk.begin(), stk.end(), lo) - stk.begin());
            steps += 20;                        // 二分约 log2(2e5) ≈ 18 步，记成常数 20
            long long b = val[stk[pos] - 1]; t = b; out.push_back(b);
        }
    }
    return out;
}
static vector<long long> bruteRun(const Data& d, long long& touched) {
    vector<long long> a, out; long long t = 0; touched = 0;
    for (const Op& o : d.ops) {
        if (o.c == 'A') { long long v = ((o.x % d.D) + (t % d.D)) % d.D; if (v < 0) v += d.D; a.push_back(v); }
        else { long long b = LLONG_MIN;
            for (size_t j = a.size() - (size_t)o.x; j < a.size(); j++) { b = max(b, a[j]); touched++; }
            t = b; out.push_back(b); }
    }
    return out;
}

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

    int negTrig[4] = {0}, ovTrig[4] = {0}, chg[4] = {0}, ins[4] = {0};
    for (int mode = 0; mode <= 3; mode++) {
        for (int s = 1; s <= 300; s++) {
            Data d = gen(s, mode);
            int c, nm, ov;
            simulate(d, c, nm, ov);
            if (nm > 0) negTrig[mode]++;
            if (ov > 0) ovTrig[mode]++;
            chg[mode] += c;
            for (const Op& o : d.ops) if (o.c == 'A') ins[mode]++;
        }
    }

    Data top = gen(1, 4);
    long long touched = 0, stkSteps = 0;
    auto t0 = steady_clock::now(); vector<long long> ob = bruteRun(top, touched);
    double msB = duration<double, milli>(steady_clock::now() - t0).count();
    t0 = steady_clock::now(); vector<long long> os = segRun(top);
    double msS = duration<double, milli>(steady_clock::now() - t0).count();
    long long segSteps = qSteps;
    t0 = steady_clock::now(); vector<long long> ok = stackRun(top, stkSteps);
    double msK = duration<double, milli>(steady_clock::now() - t0).count();
    int qcnt = 0; for (const Op& o : top.ops) if (o.c == 'Q') qcnt++;
    bool same = (ob == os && os == ok);

    if (csv) {
        for (int i = 0; i < 4; i++) {
            printf("neg%d,%d\nov%d,%d\n", i, negTrig[i], i, ovTrig[i]);
            printf("chgPct%d,%d\n", i, ins[i] ? (int)(100.0 * chg[i] / ins[i]) : 0);
        }
        printf("msB,%.0f\nmsS,%.0f\nmsK,%.0f\n", msB, msS, msK);
        printf("touched,%lld\nsegSteps,%lld\nqcnt,%d\n", touched, segSteps, qcnt);
        printf("perQ,%.1f\n", (double)segSteps / qcnt);
        printf("same,%d\n", same ? 1 : 0);
        return 0;
    }

    const char* NAME[4] = {"0 顺手（n 全正）", "1 n 可为负", "2 D 顶格、n ±10¹⁸", "3 ★ 照着溢出那条线造"};
    printf("① 三层观察（每档 300 轮）：\n\n");
    printf("   %-24s %-14s %-14s %s\n", "档位", "余数为负的轮数", "先加会溢出的轮数", "插入值被 t 改动的比例");
    for (int i = 0; i < 4; i++)
        printf("   %-24s %10d     %10d      %6d%%\n", NAME[i], negTrig[i], ovTrig[i],
               ins[i] ? (int)(100.0 * chg[i] / ins[i]) : 0);

    printf("\n② 顶格 M = 2×10⁵（%d 次查询）：\n", qcnt);
    printf("   暴力     %6.0f ms（碰了 %lld 个格子）\n", msB, touched);
    printf("   线段树   %6.0f ms（查询共走 %lld 步，每次 %.1f）\n", msS, segSteps, (double)segSteps / qcnt);
    printf("   单调栈   %6.0f ms\n", msK);
    printf("   三者答案一致：%s\n", same ? "是" : "★ 不一致！");
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

洛谷 P1198 [JSOI2008] 最大数

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

输入

输出

1★★ 先读懂「强制在线」这四个字 —— 它不是吓唬人的

2第 ① 版：原样存下来，每次往前扫 L 个

3★ 正解：一棵「预先开好、慢慢填」的线段树

4⚠⚠ 两个和线段树毫无关系的坑 —— 而官方样例两个都挡不住

5★★ 第 ③ 版：单调栈 + 二分 —— 一条和线段树一行不共享的路