那天我在 AtCoder 的题库里按照编号翻题练手列表里躺着一条AT_joi2023_yo1b_d题名是点数 (Score)。这串编号一看就有意思JOI 的过去问第 1 回预选 B 组D 题。按我的经验这种题往往不会只考一个简单的模拟但也不会把难度拉得太高属于那种想通关键一步代码 20 行就能过的题。点进去之后题目本身让我更确信了一件事它考的是一个非常经典的模型——给你一堆点回答一大堆区间计数查询。解决这个东西的思路从最直接的暴力到排序加二分再到离线加树状数组几乎串起了基础算法学习的一条完整主线。这篇文章就围绕AT_joi2023_yo1b_d 点数 (Score)展开。我会先讲讲怎么从题目编号和题名预判考点再给出一个贴合原题风格的题意模型然后从暴力分析一路讲到三种能 AC 的做法最后补充一些我自己在赛场上踩过的边界和溢出坑。适合正在备战 JOI、AtCoder Beginner Contest或者刚接触排序二分和前缀和的同学参考。1. 从题目编号 joi2023_yo1b_d 反推出题意图1.1 编号里的信息量比想象中大在 AtCoder 上遇到 JOI 过去问时题目 ID 通常会保留官方编号比如joi2023_yo1b_d。这四个部分拆开看每一段都有含义joi2023日本信息学奥林匹克JOI2023 年度相关题目。yo1byo表示预选予選1表示第 1 回b表示 B 类题组。JOI 每年第一轮预选会把题目分成 A 类、B 类等不同组别B 类通常是一般参赛者用的那一套。d这套题里的第 D 题也就是第 4 题。不要小看这套拆解。知道题目来源以后我对难度的预期会立刻校准JOI 预选 B 组的 A 题基本是纯语法题B 题开始有简单模拟C 题会有算法味道通常是贪心、二分答案、简单 DP 这一类D 题是这套题里最有区分度的一道但也不会难到需要高级数据结构。所以我在读正文之前就已经把思考范围收缩到基础算法 一点巧妙转换不会往网络流、后缀自动机那些方向瞎想。1.2 点数 (Score) 这个题名暗示了什么题名有时候比很多人以为的更有价值。日文原题名「点数」直译是得分的数量也能理解成坐标点、分数点的个数官方英文名是 Score。看到这个组合我第一时间判断它大概率不是求最大值、构造方案或者做决策而是要完成某种计数或统计。如果核心是统计得分在某个范围内的人有几个或者统计坐标轴上某个区间内有多少个点那么候选解法会迅速收敛到三类排序加二分、离散化加前缀和、离线加树状数组。这三类有一个共同特点都需要先把无序数据变成某种有序结构再通过定位端点来完成查询。这也是我从题名里得到的最大线索。1.3 题意可以模型化成什么由于我打算把这道题的完整解法讲透这里把题意整理成一个非常贴合 JOI 出题风格的模型题。如果你去 AtCoder 原题页看到的实际措辞略有不同不影响核心思路有 N 个整数 A_1, A_2, ..., A_N可以理解成 N 名学生某次考试的得分。接下来有 Q 次询问每次询问给两个整数 L, R保证 L R要求输出得分在 [L, R] 闭区间内的学生人数。关于数据范围JOI 预选 B 组 D 题通常会把 N 和 Q 都设到 2×10^5 附近A_i 和 L、R 的值可能达到 10^9。这个范围是理解后面所有优化的关键它允许 O(N log N) 的排序和每次 O(log N) 的查询但绝对不允许 O(NQ) 的暴力遍历。我特意强调这个模型是因为它太常见了。大量 AtCoder Beginner Contest 的 D 题、企业面试算法题本质都是静态数组 大量区间计数查询。把这道题吃透以后看到给一堆区间问每个区间里有多少点的描述时你就知道该往哪个方向走了。2. 暴力遍历为什么会超时以及它的真正价值2.1 最直觉的写法拿到题目第一眼最直接的想法就是对每次询问从头到尾遍历一遍数组逐个判断 A_i 是否满足 L A_i R满足就把计数器加一最后输出。这个写法正确性完全没有问题代码也就几行在小数据下跑得飞快。for (int i 0; i Q; i) { long long L, R; cin L R; int cnt 0; for (int j 0; j N; j) { if (L A[j] A[j] R) cnt; } cout cnt \n; }如果题目只是给个 1 分的小测试点这段代码完全够用。但问题在于它在大数据下没有任何活路。2.2 复杂度算清楚以后就不该犹豫暴力代码的时间复杂度是 O(NQ)。假设 N 2×10^5Q 2×10^5双层循环就是 4×10^10 次操作。现代 CPU 一秒钟大概能执行 10^8 到 10^9 次简单比较或赋值4×10^10 意味着要跑几十秒甚至更久。这在任何正常时限下都不可能通过不管是 C 还是其他语言都一样。我见过不少同学在赛场上觉得我的常数小说不定能过于是一遍一遍提交超时代码。这里我可以给出一个经验当 N 和 Q 同时达到 10^5 级别任何 O(NQ) 的双重循环都不要抱侥幸心理直接放弃。哪怕你把循环内部优化到只剩一条汇编指令次数摆在那里物理时间下不来。2.3 暴力真正的用处在于思考和验证虽然暴力解法不能 AC但它并不是一无是处。第一它可以用来拿部分分很多 JOI 和 AtCoder 题目都有小数据点专门照顾暴力选手。第二也是更重要的正解写完之后可以用暴力作为对拍器随机生成小规模数据对比两边的输出快速找出边界处理错误。从暴力里我们还能看出优化的方向。暴力慢是因为每个查询都要扫描整个数组而且每次都要比较两个条件。如果我们能预处理出一个有序结构让满足条件的元素在结构里变成连续的一段那么每次查询就不再需要扫描全部数据只需要定位两个端点。这个思路就是下一章的排序加二分。3. 排序加二分把无序查询变成端点定位3.1 有序数组让答案变成连续一段把原始数组 A 从小到大排序得到有序数组 B。对一个查询 [L, R]所有满足 L B[i] R 的元素在 B 中一定是连续的一段。这个性质来自单调性一旦遇到第一个不小于 L 的元素从它开始都是可能的候选一旦遇到第一个严格大于 R 的元素后面就都不可能了。于是问题从统计满足条件的元素个数变成了在有序数组中标记出区间的左端点和右端点然后做一次减法。打个比方图书馆的书如果按索书号排好序你想找某一类主题的书不需要从第一本翻到最后一本只要找到范围最左边的书和范围最右边的书中间的数量就是答案。3.2 lower_bound 和 upper_bound 的语义别搞混在 C 的 STL 中lower_bound返回第一个不小于给定值的位置upper_bound返回第一个严格大于给定值的位置。查询闭区间 [L, R] 时左端点用lower_bound(L)右端点用upper_bound(R)。为什么右端不用lower_bound(R)因为闭区间包含 R值为 R 的元素也要被算进去。如果右端用 lower_bound(R)你会从第一个等于 R 的位置开始截断把后面的 R 全部漏掉。这一点是整个解法里最容易出错的地方。也有同学习惯用lower_bound(R 1)代替upper_bound(R)逻辑上确实等价但我不推荐。原因是当 R 接近 long long 上限时R 1 可能溢出另外当 R 超过数组中最大值时lower_bound返回 end()如果没处理好迭代器容易越界。直接用upper_bound语义最清楚也不用做额外运算。3.3 C 参考实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin N Q; vectorlong long A(N); for (int i 0; i N; i) cin A[i]; sort(A.begin(), A.end()); while (Q--) { long long L, R; cin L R; auto itL lower_bound(A.begin(), A.end(), L); auto itR upper_bound(A.begin(), A.end(), R); cout (itR - itL) \n; } return 0; }这段代码的复杂度是排序 O(N log N)每个查询两次二分 O(log N)整体 O((N Q) log N)。对 N 和 Q 都在 2×10^5 的数据规模来说稳稳通过。3.4 Python 版实现与性能说明Python 里对应的函数是bisect_left和bisect_right分别对应 C 的lower_bound和upper_bound。实现如下import sys from bisect import bisect_left, bisect_right def main(): data list(map(int, sys.stdin.buffer.read().split())) idx 0 N, Q data[idx], data[idx 1] idx 2 A data[idx:idx N] idx N A.sort() ans [] for _ in range(Q): L, R data[idx], data[idx 1] idx 2 left bisect_left(A, L) right bisect_right(A, R) ans.append(str(right - left)) sys.stdout.write(\n.join(ans)) if __name__ __main__: main()输入一定要用sys.stdin.buffer.read()一次性读入再分割别写成循环调用input()否则光是输入解析就能差出好几倍时间。实际测试下来这段 Python 在 N Q 2×10^5 的数据下通常能跑进 2 秒如果题目时限特别紧建议换 PyPy 跑。4. 离散化加前缀和为什么仍然值得学4.1 它不会更快但它是进阶的跳板先说清楚一点对这道模型题本身离散化加前缀和在查询上并不会比排序加二分更优甚至代码更长。那为什么还要专门讲因为在竞赛里题目很少止步于纯静态查询。一旦变成支持单点修改、动态查询区间计数你就要用到坐标压缩而坐标压缩的完整名字就是离散化。另外有一类题目会多次复用相同的查询端点或者需要把端点和数组值放在同一个结构里统一处理。这时候离散化加前缀和能带来非常清爽的逻辑值域从 1e9 压缩到几十万个真正出现过的数然后像数组计数一样做前缀和。4.2 具体构造四步走离散化的本质是把稀疏的值域映射到稠密排名。完整步骤可以分成四步收集所有可能出现的值数组 A 中的每个 A_i以及每个查询的 L 和 R全部放入一个vals数组。对vals排序并去重得到一个从实际值到排名下标的映射。用一个bucket数组记录每个排名对应的人数扫描 A对每个 A_i 找到它在vals中的位置然后bucket[pos]。对bucket求前缀和查询时利用pref[r 1] - pref[l]得到区间内人数。最容易犯错的地方在第 4 步查询的 L 和 R 也许不是数组 A 中的实际得分但它们一定在vals里因为第一步就把它们收集起来了。所以不要用find之类的线性查找直接二分定位最稳妥。4.3 参考代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin N Q; vectorlong long A(N); vectorpairlong long, long long query(Q); vectorlong long vals; for (int i 0; i N; i) { cin A[i]; vals.push_back(A[i]); } for (int i 0; i Q; i) { cin query[i].first query[i].second; vals.push_back(query[i].first); vals.push_back(query[i].second); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int M vals.size(); vectorint bucket(M, 0); for (long long x : A) { int pos lower_bound(vals.begin(), vals.end(), x) - vals.begin(); bucket[pos]; } vectorint pref(M 1, 0); for (int i 0; i M; i) pref[i 1] pref[i] bucket[i]; for (auto [L, R] : query) { int l lower_bound(vals.begin(), vals.end(), L) - vals.begin(); int r lower_bound(vals.begin(), vals.end(), R) - vals.begin(); cout pref[r 1] - pref[l] \n; } return 0; }这个代码相比排序加二分显得啰嗦但它把所有值都统一放到vals里后续如果要在树状数组或线段树上维护这些值只需要把bucket换成支持修改的数据结构就行。这也是我建议初学者至少手动实现一遍的原因。5. 当题目变成动态更新离线树状数组与思想迁移5.1 得分会变化的版本很多人在刷完这道题以后会问如果比赛是实时的每次有人得分变化还要继续回答区间计数怎么办这就是经典的动态区间计数模型。假设一共有 M 次操作每次操作可能是某个人的得分从旧值变成新值也可能是询问当前得分在 [L, R] 内的人数。N 和 M 都在 2×10^5 级别。此时静态排序加二分完全失效因为每次更新都会破坏有序性重新排序一次就是 O(N)总复杂度直接爆掉。解法是离线加树状数组先把所有可能出现的得分收集起来初始得分、每次更新后的新得分、每个查询的 L 和 R全部离散化。用树状数组维护当前得分为某个离散化值的人数。更新操作在旧值的排名位置减一在新值的排名位置加一。查询操作用前缀和函数求出排名不超过 R 的人数减去排名不超过 L-1 的人数。总复杂度 O(M log M)。这个套路在 JOI 和 AtCoder 的进阶题里极其常见我建议把静态版吃透以后再自己动手写一遍这个动态版。树状数组本身代码量不大但自己实现一遍和只看别人代码是完全两种体验。5.2 另一个高频变体区间内不同值的个数还有一个变体也值得放在一起学给一个数组Q 次询问下标区间 [l, r] 内有多少个不同的值。表面上看和得分区间统计不太像但解法里有一个核心思想是相通的——把查询排序然后把无序的逐个查询变成一次有序扫描。具体做法是把所有询问按右端点 r 从小到大排序然后从左到右扫描原始数组。扫描到位置 i 时把 A_i 上一次出现的位置在树状数组里减一再把当前位置 i 加一。这样扫描到某个询问的 r 时树状数组里 [l, r] 的区间和就是区间内不同值的个数。这里的离线思想和本题先排序把区间查询变成端点定位是同一套思维模式。很多同学觉得离线处理难其实它只是把回答问题的顺序重新排了一下让数据处理更有规律可循。5.3 用一张表看清四种做法的定位做法预处理复杂度单次查询复杂度是否支持修改典型场景暴力遍历O(1)O(N)支持小数据、对拍排序加二分O(N log N)O(log N)不支持静态区间计数离散化加前缀和O((NQ) log(NQ))O(log(NQ))不支持端点固定、需要坐标压缩离线加树状数组O(M log M)O(log M)支持离线动态得分、区间不同值下次遇到同类题先在脑子里过一遍这张表基本能避开用错模型导致超时的坑。6. 判题中我真实踩过的边界与精度坑6.1 闭区间端点是头号杀手我第一次写这类题时右端点用了lower_bound(R)结果所有恰好等于 R 的得分都被漏掉样例过了但提交就是 WA。后来我养成一个习惯写完第一件事构造一组端点和实际数据重合的测试。比如N 3 A [1, 5, 10] Q 1 L 5, R 5正确答案应该是 1也就是只有得分 5 的学生被计入。如果输出 0说明右端点处理有问题如果输出 3说明边界条件完全写反了。这种小样例花不了 30 秒但能挡住大量低级错误。6.2 long long 不是可有可无的题目里 A_i 和查询值可能达到 10^9两个这样的值相加就超过 int 的 2×10^9 上限。所以读入和存储这些数值时我建议统一使用long long。尤其要小心lower_bound(R 1)这种写法。如果 R 接近 long long 上限R 1 会溢出成负数二分结果完全乱套。使用upper_bound(R)从根源上避开这个问题。下标差itR - itL本身用 int 也够因为最大就是 N但为了少想一层代码里的计数变量我也经常直接开 long long。前缀和数组如果只统计人数N 在 2×10^5 时 int 足够但如果你以后写的是总分位于某区间内的变体累加的是得分而不是人数就必须用 long long。宁可一开始写宽也别等溢出 WA 再回来改。6.3 输入优化和随机对拍C 的 cin/cout 加上ios::sync_with_stdio(false)和cin.tie(nullptr)后处理 2×10^5 的输入量没有问题。如果数据规模到 10^6我更倾向直接用scanf或自写快读。Python 那边sys.stdin.buffer.read()一次性读入是必须的逐行input()在这种数据量下性能太差。写正解之前我强烈建议留一个暴力版本用来对拍。随机生成 N 和 Q 都很小的数据把暴力输出和正解输出逐行对比。这个方法比肉眼检查边界样例可靠得多因为它会在你不知道的地方随机命中问题。6.4 赛场时间分配的心得对一道 JOI 预选 B 组的 D 题如果思路清晰从读题到 AC 应该控制在 30 到 40 分钟。排序加二分的实现非常短大量时间应该花在确认题意和边界条件上。如果卡了 10 分钟还想不到关键一步先写暴力拿部分分再在暴力基础上观察优化的方向往往比死磕正解更划算。我打比赛时有个习惯拿到题先在草稿纸上把 N、Q 的数据范围划出来提醒自己哪些复杂度不能碰。这个习惯帮我省掉了大量因为想当然而超时的提交。最后再分享一个小经验。很多人刷题喜欢按标签刷今天只刷二分明天只刷前缀和。但像joi2023_yo1b_d这种题它其实并不在乎你用排序加二分还是离散化加前缀和它考的是你看到一个点数 (Score)标题时能不能立刻意识到这是一个区间计数问题然后想到把无序变成有序把查询变成端点定位。这种建模能力比记住某个固定模板重要得多。把这题吃透以后顺手把 AtCoder 上同类型的二维偏序、离线 BIT 统计区间不同数都翻出来做一遍你会发现它们背后的核心思想几乎一模一样。希望这篇记录对正在备赛的你有点帮助。