题解 CF1215F 【Radio Stations】
Sooke
2019-09-16 11:45:20
### 简要题意
有 $n$ 个电台，第 $i$ 个电台频段在 $[l_i,\,r_i]$ 。由你在 $[1,\,m]$ 中选择主频 $f$ ，如果 $f \in [l_i,\,r_i]$ ，第 $i$ 个电台你可选择是否启用，否则无法启用。
有若干组限制形如 $u$ 和 $v$ 必须启用至少一个，或不可同时启用。请给出 $f$ 并构造电台的启用方案。无解输出 $-1$ 。
---
### 前置知识
$\text{2 - SAT}$ 。[模板题链接](https://www.luogu.org/problem/P4782) 。至于这道题，虽然明显地指示出了这类问题，但是建模是前所未有的神仙！
---
### 解题思路
按照 $\text{2 - SAT}$ 的套路，我们把一个对象拆成两个点分别表示选和不选。
于是我们掏出 $2n$ 个点，来描述 $n$ 个电台的启用方案。
但最重要的考点，还是建模。
下文用 $\text{yes}(u)$ 表示表示对象 $u$ 选的点，$\text{no}(u)$ 表示对象 $u$ 不选的点。
首先来热一热身，“若干组限制形如电台 $u$ 和电台 $v$ 必须启用至少一个”怎么在 $\text{2 - SAT}$ 中表示呢？
回忆一下，既然点表示选或不选，那么条件 $u$ 往条件 $v$ 连一条有向边表示只要条件 $u$ 满足，条件 $v$ 就必须满足。
因此，我们只要像下面一样连边：
即：$\text{no}(u) \rightarrow \text{yes}(v),\ \text{no}(v) \rightarrow \text{yes}(u)$ 。
理由很简单。当 $u$ 不选时，如果 $v$ 还不选的话，就不满足限制了，这意味着 $v$ 不得不选。反过来亦然。
下一个热身任务：若干组限制形如电台 $u$ 和电台 $v$ 不可同时启用。
连边方式异曲同工：
即：$\text{yes}(u) \rightarrow \text{no}(v),\ \text{yes}(v) \rightarrow \text{no}(u)$ 。
理由也类似。当 $u$ 选，$v$ 必须不能选，否则违反限制。反过来亦然。
热身结束。真正振奋人心的建模这才到来：如何制定唯一的 $f$ ，并表示出因为 $f \notin [l_i,\,r_i]$ ，$i$ 号电台不允许启用？
线段树优化建边？太慢！太繁琐！我们需要**前缀和的思想**！试试把区间 $[l,\,r]$ 拆成 $[1,\,l-1]$ 和 $[1,\,r]$ 来讨论。
列出以下表格：
||||
|:-:|:-:|:-:|
|$\quad f\in [1,\,l_i - 1]\quad $|$\quad f\in [1,\,r_i]\quad $|$\quad $电台 $i$ 能否启用$\quad $|
|$\text{no}$|$\text{no}$|$\text{no}$ ，此时 $f > r_i$|
|$\text{no}$|$\text{yes}$|没有限制，此时 $f \in [l_i,\,r_i]$|
|$\text{yes}$|$\text{yes}$|$\text{no}$ ，此时 $f < l_i$|
|$\text{yes}$|$\text{no}$|不存在 ，$f \in \varnothing$|
据此，提取出三个重要限制：
- 若电台 $i$ 启用，$f \in [l_i,\,r_i]$ 。
- 若 $f \in [1,\,l_i-1]$ 满足，电台 $i$ 无法启用。
- 若 $f \in [1,\,r_i]$ 不满足，电台 $i$ 无法启用。
与此同时，我们发现仅凭目前的 $2n$ 个点，不足以表示出上面的限制。
于是我们再掏出 $2(m+1)$ 个点，分别表示对于 $i = 0 \dots m$ ，$[f \le i]$ 满足或不满足。例如，用 $\text{yes}(n + i + 1)$ 表示 $f \le i$ ，用 $\text{no}(n + i + 1)$ 表示 $f > i$ 。
它们之间的连边如下：
即：$\text{yes}(n+i+1) \rightarrow \text{yes}(n+i+2),\ \text{no}(n+i+2) \rightarrow \text{no}(n+i+1)$ 。
解释：$f \le i$ 满足时，$f \le i + 1$ 必然满足。$f \le i + 1$ 不满足时，即 $f \ge i + 1$ 满足时，$f \le i$ 必然不满足。
至此，我们终于准备在两类对象之间连边了！
复读一遍那三个限制：
- 若电台 $i$ 启用，$f \in [l_i,\,r_i]$ 。
- 若 $f \in [1,\,l_i-1]$ 满足，电台 $i$ 无法启用。
- 若 $f \in [1,\,r_i]$ 不满足，电台 $i$ 无法启用。
转换成连边关系就是：
- $\text{yes}(i) \rightarrow \text{no}(n+l_i),\ \text{yes}(i) \rightarrow \text{yes}(n+r_i+1)$
- $\text{yes}(n+l_i) \rightarrow \text{no}(i)$
- $\text{no}(n+r_i+1) \rightarrow \text{no}(i)$
还有一个小细节，$f$ 不能等于 $0$ ！有个巧妙的连边是 $\text{yes}(n+1) \rightarrow \text{no}(n+1)$ ，这样 $\text{yes}(n+1)$ 成立时会造成矛盾，$\text{no}(n+1)$ 成立时刚好不会有问题。
建完图后，跑一跑 $\text{2 - SAT}$ 就行啦！判断无解的方法跟模板题一样，而有解时的 $f$ ，满足 $\text{yes}(n+f+1)$ ，$\text{no}(n+f)$ 成立 ，跑完 $\text{2 - SAT}$ 后枚举找到这个分界点即可。
---
### 代码实现
注意我的代码实现里 $n$ 个电台是从 $0$ 到 $n - 1$ 标号的。
```cpp
#include <bits/stdc++.h>
inline int read() {
char c; int x; for (c = getchar(); !isdigit(c); c = getchar());
for (x = 0; isdigit(c); c = getchar()) { x = x * 10 + c - '0'; } return x;
}
const int N = 2e6 + 5, E = 4e6 + 5;
struct List {
int tot, fst[N], nxt[E], to[E];
List() { memset(fst, -1, sizeof(fst)); }
inline void insert(int u, int v) {
nxt[tot] = fst[u]; to[tot] = v; fst[u] = tot++;
}
inline void link(int u, int v) {
insert(u, v); insert(v ^ 1, u ^ 1);
}
} e;
int n, m, m0, m1, k, c, tms, vol, dfn[N], low[N], stc[N], col[N];
bool ins[N];
inline int yes(int u) { return u << 1; }
inline int no(int u) { return u << 1 | 1; }
void tarjan(int u) {
dfn[u] = low[u] = tms++;
int pos = vol; stc[vol++] = u; ins[u] = true;
for (int i = e.fst[u]; ~i; i = e.nxt[i]) {
int v = e.to[i];
if (dfn[v] == -1) {
tarjan(v);
low[u] = std::min(low[u], low[v]);
} else if (ins[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
while (vol > pos) {
int v = stc[--vol];
col[v] = c; ins[v] = false;
} c++;
}
}
bool solve() {
for (int i = 0; i <= no(n + m); i++) { dfn[i] = -1; }
for (int i = 0; i <= no(n + m); i++) {
if (dfn[i] == -1) { tarjan(i); }
}
for (int i = 0; i <= n + m; i++) {
if (col[yes(i)] == col[no(i)]) { return false; }
} return true;
}
int main() {
m0 = read(); n = read(); m = read(); m1 = read();
for (int i = 0; i < m0; i++) {
int u = read(), v = read(); u--; v--;
e.link(no(u), yes(v));
}
for (int i = 0; i < m; i++) {
e.link(yes(n + i), yes(n + i + 1));
} e.link(yes(n), no(n));
for (int i = 0; i < n; i++) {
int l = read(), r = read();
e.link(yes(i), no(n + l - 1));
e.link(yes(i), yes(n + r));
}
for (int i = 0; i < m1; i++) {
int u = read(), v = read(); u--; v--;
e.link(yes(u), no(v));
}
if (solve()) {
for (int i = 0; i < n; i++) {
if (col[yes(i)] < col[no(i)]) { k++; }
}
for (int i = 1; i <= m; i++) {
if (col[yes(n + i)] < col[no(n + i)]) {
printf("%d %d\n", k, i); break;
}
}
for (int i = 0; i < n; i++) {
if (col[yes(i)] < col[no(i)]) { printf("%d ", i + 1); }
}
} else {
puts("-1");
}
return 0;
}
```