题解：P3588 [POI2015] PUS
wnsyou
·
·
题解
PUS
推销我的博客园。
题意
给出三个整数 n,s,m，请你构造一个整数数组 a 满足 1\leqslant a_i \leqslant 10^9(1\leqslant i \leqslant n) 以及 m 个约束条件，或判断无解。a 数组中 s 个数已经给出（保证合法）。
如果存在一个满足要求的数组 $a$，输出 `TAK`，然后在下一行输出任意一种满足要求的 $a$；否则输出 `NIE`。
### 数据范围
- $1\leqslant s\leqslant n \leqslant 10^5, 1\leqslant m \leqslant 2 \times 10^5$。
- $1\leqslant l < r \leqslant n, 1\leqslant k \leqslant r - l$。
- $l \leqslant x_1 < x_2 < \cdots < x_k \leqslant r$。
- $\sum k \leqslant 3 \times 10^5$。
## 思路
线段树优化建图。
### 初步思路：将约束条件转为建图
题目要求构造一个合法的 $a$ 数组，可以很显然的发现，当你从大到小的确定 $a$ 中的元素时，$a_i$ **越大越好。**
那么我们可以根据约束条件，建出一张由较大元素连向较小元素的有向图，最后根据这张图即可构造 $a$ 数组(用 $mi_i$ 表示所有连向它的元素的 $a_{j}$ 最小值，那么 $a_i$ 最大就为 $mi_i - 1$)。
如果是暴力建图，我们需要将每个 $x$ 中的元素都连向其他在 $[l,r]$ 中却不在 $x$ 中的元素，很明显边的数量是 $n^2$ 级别的，无法接受。
### 建图的优化：集中点
如果做过 [abc270_f Transportation](https://www.cnblogs.com/wnsyou-blog/p/17410723.html) 的话，你可以想到对于每个约束条件都建一个集中节点 $id$，将每个在 $x$ 中的元素都连向 $id$，再将 $id$ 连向每个在 $[l,r]$ 中却不在 $x$ 中的元素，边的数量便变成了 $O(m \times n + \sum k)$，似乎更差劲了。
别着急，这都是为了为下一步优化做铺垫。
注意有一个细节，题目中约束条件是严格大于，所以 $a_i = mi_i - 1$（参考上方），但对于这些集中点来说，他们**并不用严格小于连向它的元素**，即 $mi_i=a_i$，需要特别注意。
### 建图再次优化：线段树优化建图
可以发现，$id$ 暴力连向每个在 $[l,r]$ 中却不在 $x$ 中的元素的复杂度过大，**但是我们能发现，与其使用暴力连单点，我们不如转换为连接区间，这样就可以使用线段树优化建图。**
由于题目保证 $\sum k \leqslant 3 \times 10^5$，可以发现区间数量也是这个级别（只用考虑相邻两个 $x$ 之间的区间 $(x_i, x_{i+1})$），那么就好办了。
附：[线段树优化建图的模板](https://vjudge.d0j1a1701.cc/problem/CodeForces-786B)。
### 最终：整理答案和判断无解
这个很简单，使用拓扑排序即可解决，注意上面所说的细节。
无解情况如下：
- 在最优秀的构造方案中，你的 $a_i$ 肯定是尽量越大越好，所以当你发现某个 $a_i < 1$，那么必然是无解的。
- 如果你发现最初已经给定了某个元素 $a_i$ 并且 $mi_i - 1 < a_i$，那么也是不合法的。
- 如果出现了环，那么也是不合法的。
那么本题就结束了，还不理解就看代码。
### 复杂度
- 时间：$O(n+m+\sum k \log n)$。
- 空间：$O(n + m)$。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10, M = 2e5;
// ls 和 rs 用于记录线段树左右儿子，a 用于记录方案，b 是上文所说的 x，cnb 用于拓扑排序，mi 见上文
int n, m, s, rt, ncnt, ls[3 * N + M], rs[3 * N + M], a[3 * N + M], b[N], cnb[3 * N + M], mi[3 * N + M];
vector<int> g[3 * N + M];
queue<int> q;
//----------------------------------------------------------------- 线段树优化建图
void Add_edge (int x, int y) {
g[y].push_back(x), cnb[x]++;
}
void build (int id, int l, int r) {
if (l == r) {
ls[id] = l;
Add_edge(l, id);
return ;
}
int mid = (l + r) >> 1;
ls[id] = ++ncnt, rs[id] = ++ncnt;
build(ls[id], l, mid), build(rs[id], mid + 1, r);
Add_edge(ls[id], id), Add_edge(rs[id], id);
}
void modify (int id, int l, int r, int x, int y, int u) {
if (x <= l && r <= y) {
Add_edge(id, u);
return ;
}
if (l > y || r < x)
return ;
int mid = (l + r) >> 1;
modify(ls[id], l, mid, x, y, u), modify(rs[id], mid + 1, r, x, y, u);
}
//----------------------------------------------------------------- 线段树优化建图
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> s >> m, ncnt = n;
rt = ++ncnt, build(rt, 1, n);
for (int i = 1, x, y; i <= s; i++)
cin >> x >> y, a[x] = y; // 最初给定的元素直接赋值即可
for (int x, k; m--; ) {
cin >> b[0] >> x >> k, ncnt++, b[0]--;
for (int i = 1; i <= k; i++) {
cin >> b[i], g[b[i]].push_back(ncnt), cnb[ncnt]++;
if (b[i] != b[i - 1] + 1) //只用管相邻两个元素之间的区间
modify(rt, 1, n, b[i - 1] + 1, b[i] - 1, ncnt);
}
if (x != b[k]) // 最后一个区间别漏了
modify(rt, 1, n, b[k] + 1, x, ncnt);
}
for (int i = 1; i <= ncnt; i++) // 初始化为 1e9 + 1 是为了方便下方减一
mi[i] = 1e9 + 1;
q.push(rt);
while (q.size()) {
int x = q.front();
q.pop();
if (a[x]) {// 初始时有数
if (mi[x] - 1 < a[x]) { // 判断无解情况 #2
cout << "NIE";
return 0;
}
} else {
a[x] = mi[x] - (x <= n); // 细节：集中点 a[i] = mi[i]
if (a[x] <= 0) { // 判断无解情况 #1
cout << "NIE";
return 0;
}
}
for (int i : g[x]) { // 拓扑排序都会写吧
mi[i] = min(mi[i], a[x]), cnb[i]--;
if (!cnb[i])
q.push(i);
}
}
for (int i = 1; i <= n; i++)
if (a[i] <= 0) { // 如果有环的话，肯定有元素没被赋值。判断无解情况 #1
cout << "NIE";
return 0;
}
cout << "TAK\n";
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
return 0;
}
```