C++算法题—— 小C的细菌（二维偏序离线 + 树状数组 + 坐标压缩）

C++算法题—— 小C的细菌（二维偏序离线 + 树状数组 + 坐标压缩）

题目重述

小C在实验室中培育了 $n$ 个细菌。第 $i$ 个细菌的生命周期用一个闭区间 $[a_i,b_i]$ 表示。现有 $q$ 次查询，每次给出一个时间区间 $[L_j,R_j]$。对每次查询，计算生命周期完全位于该区间内（即 $L_j \le a_i$ 且 $b_i \le R_j$）的细菌数量。

输入描述

• 第一行：两个整数 $n$ 和 $q$，表示细菌数量与查询次数。
• 接下来 $n$ 行：每行两个整数 $a_i,b_i$，表示第 $i$ 个细菌的生命周期区间 $[a_i,b_i]$。
• 随后 $q$ 行：每行两个整数 $L_j,R_j$，表示一次查询的时间区间 $[L_j,R_j]$。

输出描述

• 输出 $q$ 行，每行一个整数，为对应查询的答案。

样例 1

输入
5 3
1 2
2 5
3 4
1 10
6 8
1 5
2 6
1 10输出
3
2
5

解释：
共有 5 个细菌，区间分别为 $[1,2]、[2,5]、[3,4]、[1,10]、[6,8]$。

• 查询 $[1,5]$：满足 $L\le a$ 且 $b\le R$ 的有第 1、2、3 个，共 3。
• 查询 $[2,6]$：满足的有第 2、3 个，共 2。
• 查询 $[1,10]$：5 个全部满足。

样例 2

输入
4 2
1 3
2 4
3 5
4 6
2 4
3 6输出
1
2

---

思路总览（二维偏序计数 → 离线 + 树状数组）

把每个细菌视为平面上的点 $(a_i,b_i)$。一次查询 $[L,R]$ 的条件是

$$L\le a_i\text{且}{b}_i\le R,$$

等价于统计矩形区域

$$[a_i\ge L]\cap [b_i\le R]$$

内的点数。这是一个典型的二维偏序计数问题。

关键技巧：离线排序 + 一维数据结构统计

我们只需要把“不等式的一边”转化为增量可维护的集合，另一边用前缀和统计即可。

• 对 $a$ 这一维：我们希望在处理某个 $L$ 时，手里“已加入的数据集合”恰好是所有满足 $a_i \ge L$ 的点。
  为了做到“只加不删”，应将查询按 $L$ 降序处理，并将细菌按 $a$ 降序排序。

  • 当我们从大到小依次处理 $L$ 时，可以不断把满足 $a_i \ge L$ 的新细菌加入数据结构（指针只前进不回退）。

• 对 $b$ 这一维：我们要在“已加入的点”中，统计满足 $b_i \le R$ 的数量。
  这正是前缀计数，可用树状数组（Fenwick 树）对 $b$ 的坐标进行计数与前缀和查询。

• 由于 $b$ 的取值可能很大且稀疏，使用坐标压缩：
  仅把所有 $b_i$ 收集并排序去重，查询时对 $R$ 用 upper_bound 找到不超过 $R$ 的最大压缩下标，取对应前缀和。

正确的离线流程（易错点已修正）

很多同学容易误把 $L$ 升序处理并“加入满足 $a_i \ge L$ 的点”。那样集合会随 $L$ 增大而缩小，无法只加不删。
正确方式：

1. 将细菌按 $a$ 降序排序；
2. 将查询按 $L$ 降序排序；
3. 用指针遍历细菌表：处理到某个查询 $L$ 时，把所有满足 $a_i \ge L$ 的细菌一次性“加入”树状数组（按其 $b_i$ 的压缩位置加一）；
4. 用树状数组前缀和统计 $b \le R$ 的数量即为答案。

复杂度

• 排序复杂度：$O((n+q)\log (n+q))$
• 每次加入与查询：树状数组单次为 $O(\log n)$
• 总复杂度：$O((n+q)\log (n+q))$
• 额外空间：$O(n+q)$（含坐标压缩与存储）

---

详细实现（C++，含新手友好注释）

#include <bits/stdc++.h>
using namespace std;/*小C的细菌（二维偏序）：统计满足 L <= a_i 且 b_i <= R 的点数思路：离线 + 树状数组（Fenwick）+ 对 b 维坐标压缩核心要点：1) 按 a 降序将细菌排序；2) 按 L 降序将查询排序；3) 遍历查询时，不断把 a_i >= 当前 L 的细菌“加入”树状数组；4) 在已加入集合中用前缀和统计 b_i <= R 的数量。
*/// ============ Fenwick (树状数组) 模板：支持点更新、前缀和查询 ============
struct Fenwick {int n;                  // 数组长度（压缩后的最大下标）vector<int> bit;        // 树状数组容器，1-basedexplicit Fenwick(int n=0) { init(n); }void init(int n_) {n = n_;bit.assign(n + 1, 0);  // 1..n 有效}// 低位操作：返回 x 的最低位 1 所代表的值static inline int lowbit(int x) {return x & (-x);}// 在位置 idx + val（注意 idx 从 1 开始）void add(int idx, int val) {for (; idx <= n; idx += lowbit(idx)) {bit[idx] += val;}}// 查询前缀和 sum[1..idx]int sumPrefix(int idx) const {int s = 0;for (; idx > 0; idx -= lowbit(idx)) {s += bit[idx];}return s;}
};// 细菌：生命周期区间 [a, b]
struct Bacteria {long long a, b;
};// 查询：时间区间 [L, R]，并记录原始序号 idx 以便输出
struct Query {long long L, R;int idx;
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;if (!(cin >> n >> q)) {return 0;}vector<Bacteria> bac(n);vector<long long> allB;  // 存所有 b_i，用于坐标压缩for (int i = 0; i < n; ++i) {cin >> bac[i].a >> bac[i].b;allB.push_back(bac[i].b);}vector<Query> qs(q);vector<long long> ans(q);// 读查询for (int i = 0; i < q; ++i) {cin >> qs[i].L >> qs[i].R;qs[i].idx = i;}// ===== 坐标压缩（仅对 b 进行）=====sort(allB.begin(), allB.end());allB.erase(unique(allB.begin(), allB.end()), allB.end());// 压缩后：allB[k] 是第 (k+1) 个值，对应 Fenwick 的位置 k+1auto bIndex = [&](long long b) {// 找到 b 在 allB 中的“等于”位置（存在性：b 就是来自细菌的 b_i）int pos = int(lower_bound(allB.begin(), allB.end(), b) - allB.begin()) + 1; // 1-basedreturn pos;};auto RIndex = [&](long long R) {// 对查询的 R（可能不是某个 b_i），我们需要 b <= R 的数量，// 即找到 allB 中“最后一个 <= R”的位置，对应 Fenwick 的查询下标int pos = int(upper_bound(allB.begin(), allB.end(), R) - allB.begin()); // 返回的是个数（0..m）// 这里 pos 就是 <=R 的元素个数，正好可作为 Fenwick 的前缀位置（1..m），若为 0 则没有return pos;};// ===== 排序：按 a 降序排列细菌；按 L 降序排列查询 =====sort(bac.begin(), bac.end(), [](const Bacteria& x, const Bacteria& y){return x.a > y.a;});sort(qs.begin(), qs.end(), [](const Query& x, const Query& y){return x.L > y.L;});// ===== 离线扫描 =====Fenwick fw((int)allB.size());int i = 0; // 指向当前可加入的细菌（按 a 降序）for (const auto& qu : qs) {long long L = qu.L;long long R = qu.R;// 1) 把所有 a_i >= L 的细菌加入（由于降序，只会前进 i，保证只加不删）while (i < n && bac[i].a >= L) {int idxB = bIndex(bac[i].b); // 把该细菌的 b 压缩到 1-based 下标fw.add(idxB, 1);             // 在该 b 位置 +1，表示有一个细菌++i;}// 2) 在已加入的集合内统计 b <= R 的数量（前缀和）int rPos = RIndex(R); // rPos=0 表示没有 b<=Rif (rPos <= 0) {ans[qu.idx] = 0;} else {ans[qu.idx] = fw.sumPrefix(rPos);}}// ===== 按原始顺序输出 =====for (int k = 0; k < q; ++k) {cout << ans[k] << "\n";}return 0;
}

---

正确性证明（简要）

将每个细菌映射为点 $(a_i,b_i)$。查询 $[L,R]$ 的有效性条件是：

$$a_i\in [L,+\infty ),b_i\in (-\infty ,R].$$

我们将所有细菌按 $a$ 降序排序；将所有查询按 $L$ 降序处理。当处理某个 $L$ 时，我们已把所有满足 $a_i \ge L$ 的点加入数据结构。此时只需在这些点中统计 $b_i \le R$ 的数量。对 $b$ 做坐标压缩并用树状数组维护计数，就能用前缀和在 $O(\log n)$ 时间内得到答案。由于每个点仅被“加入一次”，整体复杂度为 $O((n+q)\log(n+q))$。

---

易错点与边界情况

1. 处理顺序：必须按 $L$ 降序处理，同时按 $a$ 降序加入点，才能保证“只加不删”。

2. 坐标压缩：

   • 只需要压缩 $b$。
   • 查询时对 $R$ 使用 upper_bound(allB.begin(), allB.end(), R) 得到 $\le R$ 的元素个数作为 Fenwick 的查询位置。

3. 闭区间细节：题目是闭区间，条件为 $L \le a_i$ 且 $b_i \le R$。代码中严格按照该不等式实现。

4. 无可加入点：当当前 $L$ 很大，可能没有 $a_i \ge L$ 的点；此时树状数组为空，统计结果为 0。

5. $R$ 太小：若 $R$ 小于所有 $b_i$，则 upper_bound 返回 0，答案为 0。

6. 数据范围：若 $a,b,L,R$ 很大（如 $10^9$），压缩后数据结构仍保持在 $O(n)$ 大小，时间与空间都可控。

---

手工验证（对样例 1）

• 细菌点：$(1,2),(2,5),(3,4),(1,10),(6,8)$
• 按 $a$ 降序：$(6,8),(3,4),(2,5),(1,10),(1,2)$
• 查询降序：$[1,10],[2,6],[1,5]$

处理：

• $L=10$：无 $a\ge 10$，对 $R=10$ 统计为 0 → 暂不对应样例（因为顺序不同，最终会放回原下标）。

• 实际逐步：

  • 处理 $[1,10]$：加入 $a\ge 1$ 的全部 5 个点，统计 $b\le 10$ 前缀和 = 5。
  • 处理 $[2,6]$：前面已加入 $a\ge 2$ 的点（此时集合包含 $(6,8),(3,4),(2,5)$ 以及两个 $a=1$ 的点，但它们也是在之前一步加入的；注意：我们是离线一次插完，查询按降序进行，答案按原序号回填，逻辑正确）。对 $R=6$ 的前缀和是 $b\le 6$ 的个数：$(3,4),(2,5)$ 共 2。
  • 处理 $[1,5]$：对于 $R=5$ 的前缀和为 3（$(1,2),(2,5),(3,4)$）。
    最终按原始下标输出：3、2、5。与样例一致。

说明：实现里我们不会回撤已加入的点，而是一次性按降序把需要的点加入，在每个查询时对当前“已加入全集”做 $b\le R$ 的前缀统计，并将结果写回该查询的原始位置，因此顺序影响的是“处理顺序”，不影响最终对应查询的答案位置。

---

复杂度分析

• 排序：$O((n+q)\log(n+q))$
• 每个细菌仅加入一次：$O(n\log n)$
• 每个查询仅查询一次：$O(q\log n)$
• 总计：$$
  O\big((n+q)\log(n+q)\big)

$$

---

常见变形与拓展

• 若改成统计“部分重叠”的区间个数，需要改判定逻辑，通常不再是简单的二维偏序，可考虑扫描线或差分 + 树状数组等。
• 若要求在线回答（无需离线），需要能动态插入与删除点，可考虑平衡树/订单统计树或BIT/SegmentTree（双维或套树），实现较复杂且常数更大。
• 若还需要同时限制 $a$ 的上界或 $b$ 的下界等更多维度，可能需要更高级的数据结构（如 CDQ 分治、归并树、K-D 树等）。

---

额外测试用例（自测建议）

1. 所有细菌都被包含

输入
3 2
1 2
2 3
3 4
1 4
0 5
输出
3
3

2. 没有细菌满足

输入
3 2
5 6
6 7
7 8
1 4
2 4
输出
0
0

3. 边界相等（闭区间）

输入
3 3
2 2
3 3
4 4
2 2
3 3
2 3
输出
1
1
2

4. 大范围值（压缩验证）

输入
3 2
1000000000 1000000000
1 1000000000
123456789 987654321
1 1000000000
1000000000 1000000000
输出
3
2

---

小结

• 将“区间完全包含”转化为二维偏序：$a$ 维用降序离线“加点”，$b$ 维用树状数组做前缀计数。
• 关键是处理顺序正确与坐标压缩恰当。
• 模板化实现，适合 $n,q$ 高达 $2\times 10^5$ 级别的数据。