把“x 集合严格大于区间内其余位置”翻译成差分约束,用线段树把区间连边压到 O(log n),拓扑序推出每个位置的下界即为可行解。
OJ: roj
题目 ID: 1728
难度:提高+/省选-
标签:差分约束拓扑排序线段树优化建图构造python
创建: 2026-10-07 19:16
更新: 2026-10-07 19:16
形式化题目
给定
也就是说:区间 NIE,有解则先输出 TAK,
再输出
数据范围:
因为所有
正解
思路
第一步:把所有不等式统一成"下界"
给每个位置维护一个下界
得到的
第二步:一条信息要连多少边
最直接的翻译是:
引入一个辅助点
- 每个剩下的位置
连 权 ,即 ( 严格大于它们); 连 权 ,即 。
传递一下就是
第三步:用线段树压缩"剩下的位置"
区间
以题面样例的第二条信息
flowchart LR
L5["叶子 5<br/>a=3"] --"1"--> P2["条件点 p₂<br/>= min{a₄}"]
P2 --"0"--> L4["叶子 4<br/>a≥4"]
读作
第四步:无解怎么判
推完之后只可能有三种矛盾:
- 约束成环:拓扑排序没能剥掉所有点。线段树内部(儿子
父亲)本身无环, 所以任何环都至少经过一个条件点,而进入条件点的边权全是 , 环上权和 ,即"$a \ge a + $ 正数",矛盾。 - 下界越界:某个位置的下界
,超出值域。 - 与已知值冲突:某个已知位置被推到的下界
,和 冲突。
三种情况任一出即 NIE;都不出现时,令
为什么 一定合法
设最终下界为
(对任意合法解):沿拓扑序归纳。源点 ; 已知位置 ;对每条边 权 ,对应不等式 ,所以推完仍满足 。 满足每条信息:对空隙里的任意位置 ,设覆盖它的那个线段树节点为 。 从叶子 到 全是权 的父子边,故 ;而 权 , 于是 ;又 权 给出 , 合起来 。 - 已知位置取值精确:检查 3 通过时
(初值就是 ,且从未被推高)。
所以三种检查全部通过
实现细节:边权可以不存
图上的边权只有
| 边的来源 | 终点 | 权 |
|---|---|---|
| 儿子 |
线段树节点 | |
| 空隙节点 |
条件点 | |
| 线段树叶子 |
即:线段树节点只有权
代码
Python 短解法(与 C++ 同阶:同一张图、同一次拓扑排序):
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 19:16
# update_at: 2026-10-07 19:16
import sys
from array import array
LIMIT = 10**9 # 值域上界:任何位置的下界超过它就没有合法方案
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type IntArr = array # 4 字节整型数组,压住图的规模
type Graph = tuple[IntArr, IntArr, IntArr, IntArr, int] # (head, eto, enxt, indeg, 点数)
def decompose_range(l: int, r: int, sz: int) -> list[int]:
"""把 1-indexed 闭区间 [l, r] 拆成 O(log n) 个线段树节点编号;空区间返回空表。"""
nodes = []
lo, hi = l - 1 + sz, r - 1 + sz + 1
while lo < hi:
if lo & 1:
nodes.append(lo)
lo += 1
if hi & 1:
hi -= 1
nodes.append(hi)
lo >>= 1
hi >>= 1
return nodes
def add_edge(head: IntArr, eto: IntArr, enxt: IntArr, indeg: IntArr, u: int, v: int) -> None:
"""加一条 u -> v 的边;边权不落地,交给终点类型判定(理由见 build_graph)。"""
eto.append(v)
enxt.append(head[u])
head[u] = len(eto) - 1
indeg[v] += 1
def build_graph(sz: int, m: int, ql: IntArr, qr: IntArr,
xs: IntArr, xoff: IntArr) -> Graph:
"""把每条信息翻译成差分约束图,返回 (head, eto, enxt, indeg, 点数)。
边 u -> v 表示 a[v] >= a[u] + w。边权只有 0/1,且恰好由终点类型决定:
指向条件点(编号 >= segN)的边权为 1,那就是“严格大于”贡献的 +1;
指向线段树节点的边权为 0。所以不必再存一份边权数组。
"""
segN = 2 * sz
V = segN - 1 + m # 条件点编号 segN .. segN+m-1
head = array('i', [0]) * (V + 1)
indeg = array('i', [0]) * (V + 1)
eto = array('i', [0]) # 下标 0 当“无边”哨兵
enxt = array('i', [0])
for i in range(2, segN):
add_edge(head, eto, enxt, indeg, i, i >> 1) # 儿子 -> 父亲,权 0
for q in range(m):
p = segN + q # 条件点:含义是“x 集合中的最小值”
prev = ql[q]
for j in range(xoff[q], xoff[q + 1]):
x = xs[j]
for node in decompose_range(prev, x - 1, sz): # 剩下的位置 -> p,权 1
add_edge(head, eto, enxt, indeg, node, p)
add_edge(head, eto, enxt, indeg, p, sz + x - 1) # p -> x_i,权 0
prev = x + 1
for node in decompose_range(prev, qr[q], sz): # 末尾那段空隙
add_edge(head, eto, enxt, indeg, node, p)
return head, eto, enxt, indeg, V
def topo_bounds(n: int, sz: int, known: dict[int, int], graph: Graph) -> list[int] | None:
"""按拓扑序把下界沿出边推出去,返回每个位置的下界;约束矛盾时返回 None。
矛盾的三种来源:下界超出值域、已知位置被逼着大于给定值、约束成环。
"""
head, eto, enxt, indeg, V = graph
segN = 2 * sz
val = [0] * (V + 1)
for leaf, d in known.items():
val[leaf] = d # 已知位置以精确值当初始下界
que = [u for u in range(1, V + 1) if indeg[u] == 0]
for u in que:
if val[u] < 1:
val[u] = 1 # 没有任何约束的点取下界 1
qi = 0
while qi < len(que):
u = que[qi]
qi += 1
vu = val[u]
d = known.get(u, 0)
if vu > LIMIT or (d and vu > d): # 下界越界 / 与已知精确值冲突
return None
e = head[u]
while e:
v = eto[e]
nv = vu + 1 if v >= segN else vu # 指向条件点的边权 1,其余 0
if val[v] < nv:
val[v] = nv
indeg[v] -= 1
if indeg[v] == 0:
que.append(v)
e = enxt[e]
if len(que) != V: # 还有没被剥掉的点 → 约束成环
return None
for i in range(1, n + 1):
v = val[sz + i - 1]
if v < 1 or v > LIMIT:
return None
return val
def solve() -> None:
# 先整体转成紧凑整型数组再顺序消费:`split()` 出来的字节串列表有几千万字节,
# 直接 map 会让它一直挂着不放,这里让它转完就释放。
data = iter(array('i', map(int, sys.stdin.buffer.read().split())))
n, s, m = next(data), next(data), next(data)
sz = 1
while sz < n:
sz <<= 1 # 位置 i 的叶子编号是 sz + i - 1
known: dict[int, int] = {}
for _ in range(s):
p, d = next(data), next(data)
known[sz + p - 1] = d
ql, qr = array('i', [0]) * m, array('i', [0]) * m
xoff = array('i', [0]) * (m + 1)
xs: IntArr = array('i') # 所有信息的 x 扁平存储
for q in range(m):
ql[q], qr[q] = next(data), next(data)
k = next(data) # 题面的 k_i
xoff[q] = len(xs)
xs.extend([next(data) for _ in range(k)])
xoff[m] = len(xs)
val = topo_bounds(n, sz, known, build_graph(sz, m, ql, qr, xs, xoff))
if val is None:
print("NIE")
return
print("TAK")
print(" ".join(map(str, (val[sz + i - 1] for i in range(1, n + 1)))))
if __name__ == "__main__":
solve()C++ 正式解:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 19:16
* update_at: 2026-10-07 19:16
*/
// 一本通 1728《构造序列》(与洛谷 P3588 [POI2015] Pustynia 同题)
//
// 把每条信息翻译成差分约束:边 u -> v 权 w 表示 a[v] >= a[u] + w。
// * 线段树:儿子 -> 父亲 权 0(父亲代表区间内所有位置的最大下界)
// * 每条信息新建一个条件点 p,含义是“x 集合里的最小值”:
// - 区间内所有“剩下的位置”的线段树节点 -> p 权 1(它们都严格小于该最小值)
// - p -> 每个 x_i 权 0(x_i 不低于该最小值)
// * 已知位置直接以 d 作为下界;其余没有任何入边的点下界取 1
// 然后按拓扑序把下界往出边推,得到每个位置的最小可行取值。
// 无解的三种情况:约束成环、某个下界超过 1e9、已知位置的下界超过给定的 d。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LIMIT = 1000000000; // 值域上界,任何位置的下界超过它就没有合法方案
// ---------------- 快速读入 ----------------
static char ibuf[1 << 20];
static int ipos = 0, ilen = 0;
// 从 1MB 缓冲区里取下一个字符;缓冲区空了就再读一块,读到文件尾返回 -1。
int gc() {
if (ipos == ilen) {
ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin);
ipos = 0;
if (ilen <= 0) return -1;
}
return ibuf[ipos++];
}
// 读入一个正整数(题面输入只有正整数和空白字符)。
int read_int() {
int c = gc();
while (c < '0' || c > '9') c = gc();
int x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = gc();
}
return x;
}
int n, s, m; // 序列长度、已知位置个数、信息条数
int sz; // 线段树叶子数:>= n 的最小 2 的幂,位置 i 的叶子编号是 sz + i - 1
int segN; // 线段树节点编号 1 .. segN-1(segN = 2*sz)
int V; // 图中总点数:线段树节点 + 条件点,条件点编号 segN .. segN+m-1
vector<int> known; // known[u] = 位置叶子 u 已知的精确值,0 表示未知;非叶子恒为 0
vector<int> ql, qr; // 每条信息的左右端点 l、r
vector<int> xs; // 所有信息里给出的 x 扁平存储(题面保证每条内部递增)
vector<int> xoff; // xoff[q] = 第 q 条信息的 x 在 xs 中的起始下标
// 链式前向星:head[u] 为 u 的第一条出边编号(0 表示没有),nxt 串起同一出点的边。
// 边权只有 0/1,且恰好由终点类型决定:指向条件点(编号 >= segN)的边权为 1
// (那就是“严格大于”贡献的 +1),指向线段树节点的边权为 0。
// 利用这一点省掉单独的边权数组,最坏数据下常驻内存能压进 128MB。
struct Edge {
int to; // 终点
int nxt; // 同起点的下一条边
};
vector<int> head;
vector<Edge> e;
int edgeCnt;
vector<int> indeg; // 每个点的入度,拓扑排序用
int rangeBuf[40]; // 一次区间分解得到的线段树节点编号(最多 2*log2(1e5) < 40 个)
int rangeCnt;
// 把 1-indexed 闭区间 [l, r] 分解成 O(log n) 个线段树节点,结果写入 rangeBuf。
// l > r(空区间)时 rangeCnt 为 0。
void decompose_range(int l, int r) {
rangeCnt = 0;
int lo = l - 1 + sz;
int hi = r - 1 + sz + 1;
while (lo < hi) {
if (lo & 1) rangeBuf[rangeCnt++] = lo++;
if (hi & 1) rangeBuf[rangeCnt++] = --hi;
lo >>= 1;
hi >>= 1;
}
}
// 加一条 u -> v 的边,权重按终点类型判定(见 Edge 上方注释)。
void add_edge(int u, int v) {
edgeCnt++;
e[edgeCnt].to = v;
e[edgeCnt].nxt = head[u];
head[u] = edgeCnt;
indeg[v]++;
}
int main() {
n = read_int();
s = read_int();
m = read_int();
sz = 1;
while (sz < n) sz <<= 1;
segN = 2 * sz;
V = segN - 1 + m;
known.assign(V + 1, 0);
for (int i = 0; i < s; i++) {
int p = read_int();
int d = read_int();
known[sz + p - 1] = d; // 已知位置:a[p] 的精确值就是 d
}
ql.assign(m, 0);
qr.assign(m, 0);
xoff.assign(m + 1, 0);
xs.reserve(300005);
for (int q = 0; q < m; q++) {
ql[q] = read_int();
qr[q] = read_int();
int k = read_int();
xoff[q] = (int)xs.size();
for (int j = 0; j < k; j++) xs.push_back(read_int());
}
xoff[m] = (int)xs.size();
// 第一遍:只统计边数,好把 vector 一次性开够,避免反复扩容。
ll cnt = 2LL * sz - 2; // 儿子 -> 父亲
cnt += (ll)xs.size(); // 条件点 -> 每个 x_i
for (int q = 0; q < m; q++) {
int prev = ql[q];
for (int j = xoff[q]; j < xoff[q + 1]; j++) {
decompose_range(prev, xs[j] - 1); // x_j 之前的那段空隙
cnt += rangeCnt;
prev = xs[j] + 1;
}
decompose_range(prev, qr[q]); // 最后一个 x 之后的空隙
cnt += rangeCnt;
}
head.assign(V + 1, 0);
indeg.assign(V + 1, 0);
e.resize((size_t)cnt + 1);
edgeCnt = 0;
// 第二遍:真正建图。
for (int i = 2; i < segN; i++) add_edge(i, i >> 1); // 儿子 -> 父亲,权 0
for (int q = 0; q < m; q++) {
int p = segN + q; // 条件点:含义是“x 集合中的最小值”
int prev = ql[q];
for (int j = xoff[q]; j < xoff[q + 1]; j++) {
int x = xs[j];
decompose_range(prev, x - 1); // 剩下的位置 -> p,权 1(严格大于)
for (int t = 0; t < rangeCnt; t++) add_edge(rangeBuf[t], p);
add_edge(p, sz + x - 1); // p -> x_i,权 0
prev = x + 1;
}
decompose_range(prev, qr[q]);
for (int t = 0; t < rangeCnt; t++) add_edge(rangeBuf[t], p);
}
// 拓扑排序递推下界:val[u] = max(val[u], val[pre] + w)。
vector<int> val(V + 1, 0);
vector<int> que;
que.reserve(V);
for (int i = 1; i <= n; i++) {
int leaf = sz + i - 1;
if (known[leaf]) val[leaf] = known[leaf]; // 已知位置以精确值为下界
}
for (int u = 1; u <= V; u++) {
if (indeg[u] == 0) {
if (val[u] < 1) val[u] = 1; // 没有任何约束的点取最小值 1
que.push_back(u);
}
}
bool bad = false;
for (int qi = 0; qi < (int)que.size(); qi++) {
int u = que[qi];
if (val[u] > LIMIT) { // 下界超出值域,无解
bad = true;
break;
}
if (known[u] && val[u] > known[u]) { // 已知位置被迫大于 d,矛盾
bad = true;
break;
}
for (int ei = head[u]; ei != 0; ei = e[ei].nxt) {
int v = e[ei].to;
int w = (v >= segN) ? 1 : 0;
if (val[v] < val[u] + w) val[v] = val[u] + w;
if (--indeg[v] == 0) que.push_back(v);
}
}
if (!bad) {
for (int u = 1; u <= V; u++) {
if (indeg[u] > 0) { // 还有没被剥掉的点,说明约束成环
bad = true;
break;
}
}
}
if (bad) {
puts("NIE");
return 0;
}
for (int i = 1; i <= n; i++) {
int v = val[sz + i - 1];
if (v < 1 || v > LIMIT) {
bad = true;
break;
}
}
if (bad) {
puts("NIE");
return 0;
}
// 输出:每个位置取它的下界即为可行解。
puts("TAK");
static char obuf[1 << 22];
int op = 0;
for (int i = 1; i <= n; i++) {
int x = val[sz + i - 1];
char tmp[12];
int t = 0;
if (x == 0) tmp[t++] = '0';
while (x > 0) {
tmp[t++] = char('0' + x % 10);
x /= 10;
}
while (t > 0) obuf[op++] = tmp[--t];
obuf[op++] = (i == n) ? '\n' : ' ';
}
fwrite(obuf, 1, op, stdout);
return 0;
}复杂度
设
- 点数:
(线段树 量级 + 每条信息一个条件点)。 - 边数:线段树
条 + 共 条 + 每段空隙 条, 空隙总数为 ,故总计 。 - 时间:建图与拓扑排序都是每条边
,即同阶 。 - 空间:同阶,即图的规模本身。
代入上限
总结
这道题的骨架是"差分约束 + 拓扑排序",真正的难点在建图:
- 先把"严格大于"化成"
加 ",把构造问题变成"求每个位置的下界"。 - 用一个辅助点代表集合最小值,把
条边压成 条。 - 再用线段树把区间连边,把"逐个位置连边"压成
条。 这是"线段树优化建图"的教科书用法:点 区间的边用"儿子 父亲"的 向上边汇聚,区间 点的边用线段树分解。 - 无解判定要凑齐三条:成环 / 越界 / 与已知值冲突。第三条最容易漏——
只知道
并不等于" ",还要检查它没有被其他约束推高。
关于本题的数据与样例,有两点需要如实说明:
- 素材源里带有数据生成脚本(
data.py),说明data/是自造数据, 题面本身也可能是网络重建的,与官方原题(洛谷 P3588 [POI2015] Pustynia)的 细节可能有偏差;本题解按题面文字自行推导,未依赖任何外部题解。 - 题面样例给出的输出是
6 7 1000000000 6 3,而本解输出1 7 5 4 3。 两者都合法(读者可逐条核对上面两条信息),差别只在于本解取的是每个位置的最小可行下界, 而样例来自另一种构造。本题是"构造任意一组解",多解均判正确。 另经核对:本解与素材源的std.cpp在全部个数据点上输出逐字节一致, 且与 data/*.out完全一致。