前言
题目链接：洛谷。
题意简述
一个长度为 \(n\) 的序列，有一些位置染了色。现给出 \(m\) 条限制，第 \(i\) 条限制为 \(l_i \sim r_i\) 中有且仅有一个位置染色。求出满足这 \(m\) 中条件，染色位置个数最多为多少。
\(n \leq 2 \times 10^5\)，\(m \leq 10^5\)。
题目分析
方法 \(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\) 的最大值作为答案，因为我们需要满足所有 \(m\) 条限制。不妨用 \(f_{n + 1}\) 统计答案，这样就能完整考虑到所有限制，并求出最大值了。
时间复杂度：\(\Theta(n + m)\)。
代码
方法 \(1\)：差分约束
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 200010, M = 100010;
struct Graph {
struct node {
int to, len, nxt;
} edge[N * 2 + M * 2];
int tot = 1, head[N];
void add(int u, int v, int w) {
edge[++tot] = {v, w, head[u]};
head[u] = tot;
}
inline node & operator [] (const int x) {
return edge[x];
}
} xym;
void smller(int u, int v, int w) {
xym.add(v, u, w);
}
void bigger(int u, int v, int w) {
smller(v, u, -w);
}
void equals(int u, int v, int w) {
bigger(u, v, w);
smller(u, v, w);
}
int n, m;
int dis[N], cnt[N];
bool inq[N];
bool SPFA() {
int yzh_i_love_you = 0;
memset(dis, 0x3f, sizeof dis);
deque<int> Q; Q.push_front(0), dis[0] = 0, cnt[0] = 1;
inq[0] = true;
while (!Q.empty()) {
int now = Q.front(); Q.pop_front();
inq[now] = false;
for (int i = xym.head[now]; i; i = xym[i].nxt) {
int to = xym[i].to, w = xym[i].len;
if (dis[to] > dis[now] + w) {
dis[to] = dis[now] + w;
cnt[to] = cnt[now] + 1;
if (cnt[to] > n + 1 || ++yzh_i_love_you > 1736520) return false;
if (!inq[to]) {
inq[to] = true;
if (!Q.empty() && dis[to] < dis[Q.front()]) Q.push_front(to);
else Q.push_back(to);
}
}
}
}
return true;
}
signed main() {
#ifndef XuYueming
freopen("photo.in", "r", stdin);
freopen("photo.out", "w", stdout);
#endif
scanf("%d%d", &n, &m);
for (int i = 1, l, r; i <= m; ++i) {
scanf("%d%d", &l, &r);
equals(r, l - 1, 1);
}
for (int i = 1; i <= n; ++i) {
bigger(i, i - 1, 0);
smller(i, i - 1, 1);
}
if (!SPFA()) return puts("-1"), 0;
printf("%d", dis[n]);
return 0;
}
方法 \(2\)：动态规划
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 200010;
int n, m, mx[N], mi[N];
int Q[N], head, tail = -1;
int f[N];
signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n + 1; ++i) mx[i] = i;
for (int i = 1, l, r; i <= m; i++) {
scanf("%d%d", &l, &r);
mx[r] = min(mx[r], l);
mi[r + 1] = max(mi[r + 1], l);
}
for (int i = n; i >= 1; --i) mx[i] = min(mx[i], mx[i + 1]);
for (int i = 2; i <= n + 1; ++i) mi[i] = max(mi[i], mi[i - 1]);
for (int i = 1, j = 0; i <= n + 1; ++i) {
while (j < mx[i]) {
if (f[j] != -1) {
while (head <= tail && f[Q[tail]] <= f[j]) --tail;
Q[++tail] = j;
}
++j;
}
while (head <= tail && Q[head] < mi[i]) ++head;
if (head <= tail) f[i] = f[Q[head]] + 1;
else f[i] = -1;
}
if (f[n + 1] == -1) puts("-1");
else printf("%d\n", f[n + 1] - 1);
return 0;
}