At Least One
题意
给定一个整数 \(m\) 和 \(n\) 对数 \((a_i, b_i)\)，我们定义一个 \(f(x)\) 函数表示满足以下要求的整数序列数量：
- 整数序列为 \((1, 2, 3 \cdots m)\) 的一个子段且序列长度为 \(x\)。
- 对于 \(1 \leqslant i \leqslant n\)，满足 \(a_i\) 或者 \(b_i\) 在整数序列中出现过(可以都出现，不可以都不出现)。
求 \(f(1),f(2)\cdots f(m)\)。
数据范围
- \(1 \leqslant n \leqslant 2 \times 10^5\)。
- \(2 \leqslant m \leqslant 2 \times 10^5\)。
- \(1 \leqslant a_i < b_i \leqslant M\)。
思路
暴力
枚举左右端点，判断是否满足要求，统计答案。
时间复杂度：\(O(m ^ 2 \times n)\)。
优化
枚举左右端点就 \(T\) 了，但我们能够发现：如果 \((1, 2, 3 \cdots m)\) 的一个区间 \([l, r]\) 满足要求，则：
- 对于所有 \(1 \leqslant i \leqslant l, r \leqslant j \leqslant m\)，区间 \([i, j]\) 必然满足要求。
也就是说，对于每个左端点为 \(i\)，它对答案的贡献必然是一个区间。
枚举左端点，对于每个左端点 \(i\) 找到最小的 \(j\) 使得区间 \([i,j]\) 满足要求，那么 \(f(j - i + 1), f((j + 1) - i + 1) \cdots f(m - i + 1)\) 都要加一，这个很明显可以用差分维护。
对了，这个只能提供常数优化，重要的还是思想。
最终正解
枚举左端点 \(i\) 没问题，但暴力查找最小的 \(j\) 是会超时的，怎样优化这个 \(O(n \times m)\) 呢？
又是一顿观察，我们可以发现：随着 \(i\) 从小到大，最小的 \(j\) 是单调不减的，可以考虑使用双指针，左指针每次加 \(1\)，那么右指针怎么更新呢？
- 很显然，对于一个 \(1 \leqslant k \leqslant n\)，如果 \(a_k \geqslant i + 1\)，那么对于它来说，右指针并不需要移动，只需保持 \(j\) 就行了。
- 反之，如果 \(a_k < i + 1\)，那么 \(j\) 至少也要移动到 \(b_k\) 去，即 \(j \geqslant b_k\)。
- 而如果 \(b_k < i\)，那么就可以退出 \(i\) 循环了，后面的必然都不合法。
做法就出来了，先预处理出当左端点为 \(i\) 时，右端点至少为几，假设用 \(c\) 数组存储。
- 对于每个 \(1 \leqslant i \leqslant n\)，\(c_{a_i + 1} = \max(c_{a_i + 1}, b_i)\)。
然后就是枚举左端点 \(i\)，枚举的同时更新 \(c_i\)，取前缀最大值即可，注意左端点最大为 \(\min\limits_{1 \leqslant i \leqslant n}\{ b_i\}\)。
复杂度
- 时间：\(O(n + m)\)。
- 空间：\(O(m)\)。
Code
挑战最短代码，不服来战。
点击查看代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, m, a, b, c[N], mr, ans[N];
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
mr = m;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
c[0] = max(c[0], a), c[a + 1] = max(c[a + 1], b), mr = min(mr, b); // i = 1 时右端点至少为 max(a[i])，更新 c 数组
}
for (int i = 1; i <= mr; i++) {
c[i] = max({c[i - 1], c[i], i}); // 前缀最大值
ans[c[i] - i + 1]++, ans[m - i + 2]--; // 差分
}
for (int i = 1; i <= m; i++) {
ans[i] += ans[i - 1]; // 还原差分数组
cout << ans[i] << ' ';
}
return 0;
}