第一次在洛谷题库里刷到 P2161 [SHOI2009] 会场预约 的时候我并没有把这道 SHOI 的老题当回事毕竟题目描述就是“会场有没有冲突冲突了几个”看起来像个入门模拟。真正动手之后才发现它把区间相交判断、重载运算符、离线离散化这些数据结构基本功全部串在了一道题里而且二十分钟写出来的暴力代码还很容易在构造数据下被卡到怀疑人生。这篇文章从最朴素的 set 暴搜写法讲起再逐步升级到树状数组 set 的 O(log n) 方案把区间集合题的常见套路彻底说清楚。如果你正在备战算法竞赛或者工作中需要处理排班、会议室这类区间冲突问题这篇应该能帮你省下不少试错时间。1. 题目到底在问什么从应用场景到算法模型1.1 还原会场预约的业务逻辑题目设定非常直观PP大厦有一间礼堂用户可以提交预约申请每次申请给出一个时间段[l, r]。如果这个时间段和目前任何一条已经生效的预约存在重叠这次申请就直接作废同时系统需要输出“这次申请跟几条已有预约冲突”。如果没有冲突申请成功系统输出 0 并把新区间加入预约表。另外还有一类查询操作就是问当前一共有多少条有效预约。这里有一个很容易被忽略的前提一旦预约成功它的时间段就和所有旧预约互不相交。换句话说当前有效的预约集合一定是一个“两两不重叠的闭区间集合”。这个性质是整个题目的命门几乎所有高效解法都是围绕它展开的。举个例子假设当前有效预约是[1, 4]和[6, 9]现在来了一个申请[4, 6]。端点 4 和端点 6 刚好接上旧区间的端点。按闭区间相交的定义[1,4]和[4,6]在点 4 上重叠[6,9]和[4,6]在点 6 上重叠所以这次申请应该被拒绝输出冲突数量 2。这些细枝末节如果不提前确认后面写判断条件时很容易吃大亏。1.2 从输入输出抽象出算法模型原题的输入是一系列操作第一行是操作总数 n后续每行要么是A l r表示一次预约申请要么是B表示查询当前预约总数。n 最大可以到 20 万级别所以单个操作的复杂度不能太高至少要朝 O(log n) 或更优去设计。把它剥掉场景外衣之后真正的算法模型是这样的维护一个集合 S集合里每个元素是一个闭区间[l, r]。S 中任意两个区间互不相交。插入操作给定新区间[l, r]先计算 S 中有多少个区间与它相交。若数量为 0则把新区间加入 S无论成不成功都输出这个数量。查询操作输出当前 S 的大小。所以这道题本质上就是一个“动态区间集合上的相交计数问题”。数学化之后反而更好想不要被“会场”“预约”这些词带偏盯住区间集合的性质去设计数据结构。1.3 互不相交带来的关键性质既然 S 中任意两个区间互不相交那么把 S 里的区间按照左端点从小到大排序后整个结构会非常干净。假设当前要查询的区间是[l, r]我只需要关心两类旧区间第一类是“前驱”区间也就是左端点小于 l 的那些区间里最大的那一个。它可以跨越 l与新区间相交如果它都不跨越 l那更左边的区间就更不可能跨越 l 了。这类区间最多只有一个不可能出现两个否则这两个旧区间会一起覆盖点 l它们自己就先重叠了。第二类是左端点落在[l, r]范围内的所有区间。这些区间只要左端点在查询范围内右端点又必然大于等于左端点所以必然和[l, r]相交。至于左端点大于 r 的区间整个都在查询区间右边不可能相交左端点小于 l 且右端点也小于 l 的区间整个都在查询区间左边也不可能相交。这个“前驱唯一 左端点区间计数”的结论就是后面所有优化方案的基石。暴力解法用它少走弯路树状数组优化更是直接把“左端点计数”这一步变成了 O(log n) 的前缀和查询。2. 用 set 维护预约表重载运算符是第一块敲门砖2.1 为什么需要重载运算符C 的set是一个平衡二叉搜索树它的插入和查找都依赖元素的“严格弱序”。如果集合里的元素是一个自定义结构体我必须告诉它“什么叫小于”否则它根本没法维护有序结构。对于区间[l, r]最自然也是最适合这道题的排序规则就是先按左端点 l 从小到大排左端点相同时再按右端点 r 排。struct Node { int l, r; bool operator (const Node other) const { if (l ! other.l) return l other.l; return r other.r; } };这里有几个细节值得注意。第一operator 必须声明为const成员函数否则set的比较逻辑会报错。第二这套排序规则虽然写了 r 作为第二关键字但实际运行时 S 里不可能出现两个左端点相同的区间。为什么因为两个左端点相同的区间如果同时存在它们必然都包含这个左端点也就必然相交违背了预约集合互不相交的前提。第三排序规则只影响区间在树里的位置不改变区间的语义这和数学上的偏序关系是两码事。有了这个结构体我就可以用std::setNode来维护所有有效预约。插入一条新区间时set会按照左端点把它放到正确的位置查找时也可以借用lower_bound快速定位。2.2 lower_bound 的哑元技巧这是整道题最容易写懵的地方。我想找“第一个左端点不小于 x 的区间”但set的lower_bound需要传入一个和元素同类型的参数不能直接传一个整数。所以需要临时构造一个只有左端点有意义的结构体auto it st.lower_bound(Node{x, INT_MIN});这个Node{x, INT_MIN}就是所谓的“哑元”。它的右端点取极小值只是一个占位符真正参与排序的是左端点 x。由于operator 首先比较左端点所以INT_MIN只要不大于任何合法右端点就不会对查找结果产生干扰。你可能想问右端点给 0 行不行在绝大多数情况下行因为合法区间的右端点至少是左端点而左端点通常从 1 开始。但最稳妥的写法还是INT_MIN这样即使题目允许 0 或者负数坐标也不会出问题。之前在别的题里我就因为哑元右端点给太大导致lower_bound跳过了一批左端点相同的元素白白调了半天。2.3 用例子感受区间分布规律光说理论不够直观我拿一组数据来走一遍。假设当前有效预约是[1, 2], [4, 5], [7, 8], [10, 12]查询[6, 9]时lower_bound(Node{6, INT_MIN})返回第一个左端点不小于 6 的区间也就是[7, 8]。它的前驱是[4, 5]右端点 5 小于 6所以前驱不冲突。再看左端点落在[6, 9]范围内的区间只有[7, 8]一个所以冲突数量是 1。再查询[2, 5]。lower_bound(Node{2, INT_MIN})返回[4, 5]前驱是[1, 2]它的右端点 2 大于等于查询左端点 2所以前驱冲突计数 1。左端点落在[2, 5]范围内的区间是[4, 5]也冲突计数再加 1。总冲突数量 2。可以看到只要抓住“前驱唯一”和“左端点区间内的区间必然相交”就完全不需要遍历全部旧区间来判断。这个规律其实就是第 1 章里那个关键性质的直接应用。3. 先写一个不完美的暴力 set 解法3.1 核心 add 函数逐行拆解在引入树状数组之前先看看不带优化的 set 暴力写法是什么样子。它虽然时间复杂度不够优但是逻辑最直白非常适合作为理解切片void add(int l, int r) { int cnt 0; auto it st.lower_bound(Node{l, INT_MIN}); // 第一步检查前驱区间是否跨过 l if (it ! st.begin()) { auto pre prev(it); if (pre-r l) cnt; } // 第二步统计左端点落在 [l, r] 内的所有区间 while (it ! st.end() it-l r) { cnt; it; } // 第三步没有冲突才真正插入 if (cnt 0) { st.insert(Node{l, r}); } cout cnt \n; }第一步使用prev(it)拿到前驱。这里必须先判断it ! st.begin()否则对begin()做prev是未定义行为。第二步的while循环从it开始只要左端点不超过 r 就一路计数。因为set里的区间是按左端点有序排列的所以一旦发现某个区间左端点大于 r后面所有区间都不可能相交。注意这个暴力写法里第二步的 while 循环是唯一会“遍历多个冲突区间”的地方。如果当前查询的[l, r]很大而旧区间又很多这个循环可能要走非常久。这就是它不完美的地方。3.2 为什么会被卡成 O(n^2)理论上讲这个暴力解法的单次操作复杂度是 O(k log n)其中 k 是与查询区间相交的旧区间数量。问题是 k 可以很大而且可以每次查询都很大。我构造一个反例给你看先用 n/2 次 A 操作插入一大批互不相交的“细长条”区间比如[1,1]、[3,3]、[5,5]这种交错排布的小区间。然后每次查询都用一个覆盖整个坐标轴的大区间[1, 1000000]。这样每一次 A 操作while 循环都要把当前所有旧区间全部扫一遍。随着旧区间数量越来越多总复杂度就趋近于 O(n^2)在 n20 万时直接 TLE。我当时第一次提交就是被这样一组数据卡掉的。后来在洛谷讨论区看到有人说“这题数据其实不强set 暴力能过”但我自己实测在极端数据下确实不行。所以如果追求稳定 AC不能停在暴力 set必须再往前一步。3.3 从暴力到优化的关键一步回头盯着暴力代码看真正拖慢速度的只有 while 循环它在逐个数“左端点落在 [l, r] 内的区间数量”。而前驱检查永远只检查一个区间不会成为瓶颈。所以我开始想能不能不遍历这些区间而是用一个支持动态插入和区间求和的数据结构直接算出“当前有效预约中左端点落在 [l, r] 内的总个数”这个思路顺理成章地指向树状数组。因为区间左端点是一个整数只要把所有可能出现的左端点离散化就可以用 BIT 维护每个左端点出现次数的前缀和。4. 树状数组 set 的线性对数解法4.1 离线离散化先看清所有可能的左端点要使用树状数组第一件事是把“左端点”这个维度离散化。做法并不复杂在读入所有操作之前先把所有 A 操作里出现的左端点 l 收集起来排序去重得到一个坐标数组coord。这一步是离线的因为无论一个 A 操作最终是否会被拒绝它的左端点 l 都已经固定出现在输入里了。离散化的理由是只有这些位置才可能成为某个成功预约的左端点。其他坐标就算在区间内部出现也永远不会承担“左端点计数”的职责。所以我可以放心地把坐标范围从 10^9 压缩到最多 n 个不同的值。sort(coord.begin(), coord.end()); coord.erase(unique(coord.begin(), coord.end()), coord.end()); int m coord.size();后面所有 BIT 操作都在 1..m 的下标上进行。4.2 前驱冲突查询还是交给 set树状数组负责“左端点区间计数”但前驱检查依然需要知道“最后一个左端点小于 l 的区间是谁”。这件事用set最方便auto it st.lower_bound(Node{l, INT_MIN}); if (it ! st.begin()) { auto pre prev(it); if (pre-r l) cnt; }这里的逻辑和第 3 章完全一样。之所以前驱最多只有一个是因为集合里任意两个区间都互不相交。如果pre-r l说明前驱区间覆盖了查询区间的左端点二者相交否则前驱区间完全在左侧更早的区间更不可能跨过来。4.3 区间内左端点计数BIT 前缀和之差现在到了最关键的部分。假设我已经把每个成功预约的左端点插入了 BIT那么想知道左端点落在[l, r]内的预约数量其实就是两个前缀和相减int rankR upper_bound(coord.begin(), coord.end(), r) - coord.begin(); // 0..m int rankL lower_bound(coord.begin(), coord.end(), l) - coord.begin() 1; // 1..m int cross sum(rankR) - sum(rankL - 1);这里一定要把rankR和rankL算清楚rankR用upper_bound表示“坐标不超过 r 的最后一个离散化位置”的前一个下标。如果 r 比所有左端点都大rankR就等于 m如果 r 太小rankR等于 0。rankL用lower_bound找到第一个不小于 l 的坐标再转成 1-based 下标。因为 l 一定出现在coord里所以这个下标一定有效。sum(rankR) - sum(rankL - 1)计算的是离散化坐标在[l, r]范围内的左端点总数。我再用一个例子说明这里为什么容易错。假设coord [5, 7, 9, 12]当前只有一条预约[5, 5]所以 BIT 在坐标 5 的位置有一个 1。现在查询[5, 5]rankR upper_bound(所有, 5)返回第一个大于 5 的坐标下标即 index 1。rankL lower_bound(所有, 5)返回 index 0再加 1 得到 1。cross sum(1) - sum(0) 1。如果把rankL错误写成upper_bound(...)就只会得到sum(1) - sum(1) 0白白漏掉左端点恰好等于 l 的预约。这种边界问题在比赛里特别坑人我建议直接把这段截图放在自己笔记里。4.4 插入预约时同步维护两个结构当cnt 0时申请成功。这时需要同时做两件事st.insert(Node{l, r}); int pos lower_bound(coord.begin(), coord.end(), l) - coord.begin() 1; add(pos, 1);st.insert让 set 能够继续支持前驱查询add(pos, 1)让 BIT 能够统计这个左端点。因为申请成功的前提是与所有旧预约都不相交所以插入之后集合仍然满足“两两互不相交”的性质后面的前驱检查和 BIT 查询都能继续正确运行。4.5 完整代码C17 可 AC 版把所有逻辑串起来就是下面这段可以稳定应对 n20 万的代码。我在关键位置加了注释你可以直接拿去对照着改。#include bits/stdc.h using namespace std; const int MAXN 200005; struct Node { int l, r; bool operator (const Node other) const { if (l ! other.l) return l other.l; return r other.r; } }; setNode st; // 维护所有有效预约按左端点排序 vectorint coord; // 所有可能作为预约左端点的坐标 int bit[MAXN], m; int lowbit(int x) { return x -x; } void add(int idx, int val) { for (; idx m; idx lowbit(idx)) { bit[idx] val; } } int sum(int idx) { int res 0; for (; idx 0; idx - lowbit(idx)) { res bit[idx]; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectortuplechar, int, int ops; ops.reserve(n); for (int i 0; i n; i) { char op; cin op; if (op A) { int l, r; cin l r; ops.push_back({op, l, r}); coord.push_back(l); // 离线收集可能出现的左端点 } else { ops.push_back({op, 0, 0}); } } sort(coord.begin(), coord.end()); coord.erase(unique(coord.begin(), coord.end()), coord.end()); m (int)coord.size(); for (auto [op, l, r] : ops) { if (op B) { cout sum(m) \n; // 当前有效预约总数就是 BIT 总和 continue; } int conflict 0; // 检查前驱区间 auto it st.lower_bound(Node{l, INT_MIN}); if (it ! st.begin()) { auto pre prev(it); if (pre-r l) conflict; } // 左端点落在 [l, r] 内的预约数量 int rankR upper_bound(coord.begin(), coord.end(), r) - coord.begin(); int rankL lower_bound(coord.begin(), coord.end(), l) - coord.begin() 1; conflict sum(rankR) - sum(rankL - 1); if (conflict 0) { st.insert(Node{l, r}); int pos lower_bound(coord.begin(), coord.end(), l) - coord.begin() 1; add(pos, 1); } cout conflict \n; } return 0; }这段代码在洛谷 P2161 上实测是稳过的。核心操作只有set::lower_bound、set::insert、两次 BIT 前缀和、一次 BIT 单点修改全部都是 O(log n)整体 O(n log n)完全覆盖 20 万的数据范围。4.6 三种解法横向对比为了让你有全局观我把常见的几种做法拉一个表解法单次 A 操作复杂度是否容易被构造数据卡代码量适用场景暴力 set 枚举冲突区间O(k log n)k 为冲突区间数会k 可以很大很短理解思路、小数据BIT set 离线离散化O(log n)不会中等竞赛标准解法线段树区间染色O((k 1) log n)冲突多时会退化较长区间覆盖类变体题线段树区间染色在这个题目里其实不是最优选择它更适合“区间染色后询问某个点颜色”或者“区间整体被覆盖次数”这类问题。而 BIT set 的思路恰恰抓住了本题“只需要关心左端点计数”的特征所以又简单又快。5. 实战中的常见问题与避坑记录5.1 端点是否算相交闭区间判断必须用 这是第一道坎。闭区间[a, b]和[c, d]相交的判定条件是a d c b如果两个区间中左边的那个左端点更小那么相交条件可以简化为“右端点 另一个左端点”。也就是说如果查询区间是[l, r]前驱区间要让pre-r l才算相交端点相碰也算冲突。我一开始图省事写成了pre-r l结果[1, 2]和[2, 3]被判断成不相交连续 WA 了好几发。赛后复盘才发现题目定义的“重叠”按闭区间语义来算两个区间的公共端点也是重叠。5.2 lower_bound 的哑元右端点到底给多少我在第 2 章说过右端点给INT_MIN最保险。如果只给 0在大多数正常坐标下没问题但一旦题目出现负数坐标或者更奇怪的边界就可能出问题。另外要注意哑元写法必须和重载运算符配套如果你的operator 是先比较右端点再比较左端点那哑元的设计就完全不同。这个配套关系可以参考自己的排序规则随时调整。还有个容易被忽略的点st.lower_bound(Node{l, INT_MIN})返回的是第一个“左端点不小于 l”的元素而不是“左端点等于 l”的元素。正因为如此它也可能指向左端点远大于 l 的区间这时候前驱检查照常做BIT 的区间计数也照常做不需要额外判断it-l的具体值。5.3 prev(it) 的迭代器安全操作set的迭代器是双向迭代器不像vector那样支持it - 1。要拿前驱必须用prev(it)。但是如果it已经是begin()prev(it)就是未定义行为轻则 RE重则直接崩溃。正确姿势是if (it ! st.begin()) { auto pre prev(it); ... }还有一个迭代器失效问题虽然这道题没碰到但做其他区间题时很容易踩如果在循环里调用了st.erase(it)那么it就失效了再执行it是错的。正确做法是先用auto nxt next(it)保存后继或者用it st.erase(it)接收返回值。这道题因为冲突时并不删除旧区间所以相对安全但我建议把这两个习惯焊在脑子里。5.4 BIT 下标和离散化坐标的一致性这是新手最容易弄混的地方。coord里存的是真实坐标BIT 的下标是1..m的离散化位置。每次从真实坐标映射到下标的步骤是int pos lower_bound(coord.begin(), coord.end(), x) - coord.begin() 1;查询“左端点落在[l, r]内”时我是用upper_bound(coord.begin(), coord.end(), r)作为前缀上界用lower_bound(coord.begin(), coord.end(), l)转成下界。这两个边界函数刚好一左一右卡住了闭区间[l, r]不会多也不会少。如果这里把upper_bound和lower_bound写反或者忘了把rankL转成 1-based最常见的症状就是查询区间正好包含某个旧预约左端点时答案少 1。这个 bug 特别隐蔽因为大部分数据下答案只是差一点很难一眼看穿。5.5 为什么不能只看“某一个区间”判断相交有一种很天真的尝试是用set找到一个看起来最接近的区间然后只判断它是否和[l, r]相交。这显然不够。比如旧区间是[1, 4]和[6, 9]查询[3, 8]两个旧区间都分别和查询相交但没有任何一个旧区间能同时代表另一个。所以必须老老实实把“前驱”和“左端点区间计数”两部分加起来不能试图用一个点或一个区间概括整个集合。顺着这个思路再往前想如果一个题目不保证旧区间互不相交或者允许区间合并替换那模型会完全变样需要用线段树维护覆盖次数之类的更重量级手段。正是因为 P2161 有“互不相交”这个强约束BIT set 才能以这么轻的代价解决问题。最后说点个人体会。我从最早见到这道题到现在比较深的感受是区间问题的难处往往不在写代码而在能否抓住集合元素互不相交这个强约束。一旦意识到“相交区间只可能出现在前驱和一段左端点落在查询范围内的元素中”整个题就从枚举退化成了计数。后来我做多道动态区间题只要题目保证区间互斥第一反应都是先排序再用 BIT 或线段树去数左端点这套打法的性价比真的很高。如果你正在刷题建议把 P2161 和它的同类题放在一起对比会比单刷一遍收获大很多。