1 - 模型描述
在数轴上，有 \(n\) 个区间，对于第 \(i\) 个区间覆盖的区间为 \([l_i, r_i]\) ，现在你要求出所有 \(k \in [1, n]\)，恰好被 \(k\) 个区间覆盖的点的个数。
2 - 做法
对于模型的描述，很容易想到用差分解决。但是通常题目的数据范围不适合常规差分，如 \(1 \leq l_i, r_i, \leq 10^{18}\)。因此考虑离散化。用 \(map\) 来记录每一个端点的差分值，在读取区间 \([l, r]\) 的时候进行如下操作：
\[event[l]+1, \quad event[r+1]-1
\]
我们用扫描线来扫描出现过的每一个端点，同时使用变量 \(sum\) 来记录当前覆盖区间的数量，\(last\) 来记录上一个扫描到的端点的位置。
每当我们扫描到一个端点 \(i\)，我们先更新答案 \(ans[sum] = ans[sum] + (i - last)\)，再更新当前覆盖区间的数量 \(sum = sum + diff[i]\).
3 - 例题 - CF1000C
题目大意：
给你 \(n\) 个区间，求被这些区间覆盖层数为 \(k\) \((1 \leq k \leq n)\) 的点的个数。
输入格式：
第一行一个整数 \(n\) \((n \leq 2∗10^5)\)
以下 \(n\) 行，每行有两个整数，即这个区间的左右端点 \(l,r\) \((0 \leq l \leq r \leq 10^{18})\)
输出格式：
\(n\) 个整数，即每个被覆盖层数对应的点的个数。
思路：
本题思路与模型处理方式基本一致，即：
- 对每个区间的端点进行离散化的差分处理。
- 扫描每一个端点，在加上端点上的差分值的同时维护答案。
参考代码：
#include <bits/stdc++.h>
using namespace std;#define endl '\n'
#define i64 long longint main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int n;cin >> n;map<i64, int> event;for (int i = 1; i <= n; i ++ ) {i64 l, r;cin >> l >> r;event[l]++, event[r + 1]--;}i64 sum = 0, last = -1;vector<i64> ans(n + 1);for (auto& [cur, diff] : event) {ans[sum] += cur - last;sum += diff;last = cur;}for (int i = 1; i <= n; i ++ ) cout << ans[i] << ' ';
}
4 - 练习
ABC221D: https://atcoder.jp/contests/abc221/tasks/abc221_d