P2184 贪婪大陆
点击查看原题
P2184 贪婪大陆
题目背景
面对蚂蚁们的疯狂进攻，小 FF 的 Tower defence 宣告失败……人类被蚂蚁们逼到了 Greed Island 上的一个海湾。现在，小 FF 的后方是一望无际的大海，前方是变异了的超级蚂蚁。小 FF 还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造 SCV 布置地雷以阻挡蚂蚁们的进攻。
题目描述
小 FF 最后一道防线是一条长度为 \(n\) 的战壕，小 FF 拥有无数多种地雷，而 SCV 每次可以在 \([L, R]\) 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小 FF 在某些时候可能会询问你在 \([L',R']\) 区间内有多少种不同的地雷，他希望你能尽快的给予答复。
输入格式
第一行为两个整数 \(n\) 和 \(m\)，\(n\) 表示防线长度，\(m\) 表示 SCV 布雷次数及小 FF 询问的次数总和。
接下来有 \(m\) 行，每行三个整数 \(q,l,r\)：
- 若 \(q=1\)，则表示 SCV 在 \([l, r]\) 这段区间布上一种地雷；
- 若 \(q=2\)，则表示小 FF 询问当前 \([l, r]\) 区间总共有多少种地雷。
输出格式
对于小 FF 的每次询问，输出一个答案（单独一行），表示当前区间地雷种数。
输入输出样例 #1
输入 #1
5 4
1 1 3
2 2 5
1 2 4
2 3 5输出 #1
1
2说明/提示
数据规模与约定
- 对于 \(30\%\) 的数据，\(0 \le n\)，\(m \le 1000\)。
- 对于 \(100\%\) 的数据，\(0 \le n\)，\(m \le 10^5\)。
暴力
遇到这类可能是线段树或者树状数组的题目，可以先写一发暴力找找思路
map<int, set>
这道题目我的第一反应是开一个map<int, set<int>>来维护每个点存了多少雷。但是根据deepseek这样会把区间问题退化成点上的集合问题，丢弃了区间的结构信息。因此该暴力方案不可行。
vector<pair<int, int>>
存储
这个时候，我们观察这个map<int, set<int>>，发现同一种地雷的信息被重复存储了\(r-l+1\)次，信息冗余。事实上，只要存储区间的端点就可以保证记录这一次摆放的地雷的信息。又因为保证每一次在区间上放的地雷种类与之前的不同，因此，我们可以维护一个长度不超过m的数组vector<pair<int, int>> a来存储每一次摆放的地雷信息。
查询
存储很显然是\(O(1)\)的，查询的时候
int cnt = 0;
for (auto[ql, qr] : a)if (ql <= r && qr >= ql) ++ cnt;
cout << cnt << '\n';
这样是固定\(O(m)\)的查询
树状数组
看到这里，区间修改+单点查询的优化，非常自然地想到树状数组。
点击查看完整代码
#include <bits/stdc++.h>
using namespace std;template<typename T>
struct BIT
{int n; vector<T> tr;BIT(int n_){n = n_;tr.assign(n + 1, 0);}void add(int i, T delta){while (i <= n){tr[i] += delta;i += i & -i;}}int sum(int i){int s = 0;while (i > 0){s += tr[i];i -= i & -i;}return s;}
};int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, m; cin >> n >> m;BIT<int> bitL(n), bitR(n);while (m -- ){int op, l, r;cin >> op >> l >> r;if (op == 1){bitL.add(l, 1);bitR.add(r, 1);}else{int ans = bitL.sum(r) - bitR.sum(l - 1);cout << ans << '\n';}}return 0;
}
先统计所有满足 \(l_i ≤ R\) 的区间数（即 bitL.sum(R)），再减去其中那些不满足 \(r_i ≥ L\) 的区间数（即 \(r_i < L\) 的区间数）。
而 \(r_i < L\) 等价于 \(r_i ≤ L-1\)，数量正好是 \(bitR.sum(L-1)\)。
所以 \(bitL.sum(R) - bitR.sum(L-1)\) 统计的就是同时满足 \(l_i ≤ R\) 且 \(r_i ≥ L\) 的区间数。
因此，两种方法在数学上完全等价。树状数组只是用两个前缀和快速算出 \(\lvert U\rvert\) 和 \(\lvert B \rvert\)，避免了遍历所有区间。