P3084
XuYueming
·
·
题解
前言
题目链接：洛谷。
更好的体验。
题意简述
一个长度为 n 的序列，有一些位置染了色。现给出 m 条限制，第 i 条限制为 l_i \sim r_i 中有且仅有一个位置染色。求出满足这 m 中条件，染色位置个数最多为多少。
## 题目分析
### 方法 $1$：差分约束
区间问题使用前缀和，退化成关于两端点的限制：$v_{r_i} - v_{l_i - 1} = 1$，其中 $v_i$ 表示 $1 \sim i$ 中有多少染色的位置。以及题目本身的限制：$v_{i} - v_{i - 1} \in [0, 1]$，建图后差分约束跑一跑即可。
我们求 $\max v_n$，使用最短路算法。
无解情况等价于存在负环，最短路不存在。
但是显然会超时，如何优化？SPFA 经典优化：SLF 优化。嗯，还差一个点，循环次数超过魔法数字 $1736520$ 就无解。就水过去了。
### 方法 $2$：动态规划
差分约束显然不是正解。序列问题，决策是当前点是否染色，可以使用 DP 解决。
我们设 $f_i$ 表示 $i$ 染色时 $1 \sim i$ 染色的位置的个数的最大值。转移的时候枚举上一次染色的位置 $j$，有转移方程：
$$
f_i = \max _ {\text{meet given conditions}} \{ f_j \} + 1
$$
时间复杂度什么的先不谈，考虑怎么判断一个 $j$ 是否合法。
有一个 trick：**「恰好」等价于「不少于并且不大于」**。
对于本题，恰好区间染色了一个位置，拆成两个限制，即至少染色一个位置，至多染色一个位置。
先考虑前者。由于 $(i, j)$ 中没有染色，如果其中存在一个限制区间就会不合法。所以我们求得 $mi_x$ 表示右端点在 $x$ 左边，左端点的最大值。$j$ 需要满足 $j \geq mi_i$。
再考虑后者。如果一个区间同时包括了 $i$ 和 $j$，那么也是不合法的。我们求得 $mx_x$ 表示右端点在 $x$ 及右边，左端点的最小值。$j$ 需要满足 $j \lt mx_i$。
预处理扫一扫是简单的。
转移方程变成：
$$
\large f_i = \max _ {j = mi_i} ^ {mx_i - 1} \{ f_j \} + 1
$$
由于 $mx$ 和 $mi$ 单调不降，直接上单调队列就行了。注意如果我们记无效的 $f_i = -1$，则上式中的 $\max$ 需要满足 $f_j \neq -1$，如果没有满足条件的 $j$，那么 $f_i = -1$。
注意到我们不能直接取 $f$ 的最大值作为答案，因为我们需要满足所有 $m$ 条限制。不妨用 $f_{n + 1}$ 统计答案，这样就能完整考虑到所有限制，并求出最大值了。
时间复杂度：$\Theta(n + m)$。
**Update on 2024.11.2**：寻找到 $f$ 的性质，省略单调队列。
经过打表发现 $f$ 是单调递增的，所以单调队列可以换成双指针，维护 $\lt mx_i$ 的 $j$ 中，最后一个 $f_j \neq -1$ 的 $k$。转移的时候判断 $k$ 是否 $\geq mi_i$，转移即可。时间复杂度没有变化。
**详细证明**：
使用第二数学归纳法。假设所有 $j \lt i$ 满足 $f_j$ 具有单调性。如果能推出 $f_i \geq f_{i - 1}$ 即证。
有 $mx_i \geq mx_{i - 1}$，那么在 $mx_{i - 1} + 1 \sim mx_i$ 可能存在 $\geq f_{mx_{i - 1}}$ 的 $f$，因为所有 $j \lt i$ 满足 $f_j$ 具有单调性，那么 $f_i$ 就能从这里转移过来，从而 $\geq f_{i - 1}$。
## 代码
### 方法 $1$：差分约束
见[我的博客](https://www.cnblogs.com/XuYueming/p/18397834)。
### 方法 $2$：动态规划
### 单调队列
见[我的博客](https://www.cnblogs.com/XuYueming/p/18397834)。
### 双指针
```cpp
#include <cstdio>
const int MAX = 1 << 23, N = 200001;
int n, m, l, r, mx[N], mi[N], f[N];
char buf[MAX], *p(buf), *e(buf + MAX);
#define getchar() (p == e && fread(p = buf, 1, MAX, stdin), *p++)
[[always_inline]] inline void read(int &x) {
x = 0; char ch = getchar();
for (; ch < 48; ch = getchar());
for (; 48 <= ch; ch = getchar())
x = (x << 3) + (x << 1) + (ch ^ 48);
}
[[always_inline]] inline void tomin(int& a, int& b) { b < a && (a = b); }
[[always_inline]] inline void tomax(int& a, int& b) { b > a && (a = b); }
main() {
fread(buf, 1, MAX, stdin), read(n), read(m);
for (register int i(1); i <= n + 1; ++i) mx[i] = i;
for (; m--; ) read(l), read(r), tomin(mx[r], l), tomax(mi[r + 1], l);
for (register int i(n); i; --i) tomin(mx[i], mx[i + 1]);
for (register int i(1), j(0), k(0); i <= n + 1; ++i, tomax(mi[i], mi[i - 1])) {
for (; j + 1 < mx[i]; ~f[++j] && (k = j));
f[i] = k >= mi[i] ? f[k] + 1 : -1;
}
~f[n + 1] ? printf("%d", f[n + 1] - 1) : puts("-1");
}
```