构造序列

GitHub跳转原题关系图返回列表

把“x 集合严格大于区间内其余位置”翻译成差分约束,用线段树把区间连边压到 O(log n),拓扑序推出每个位置的下界即为可行解。

OJ: roj

题目 ID: 1728

难度:提高+/省选-

标签:差分约束拓扑排序线段树优化建图构造python

创建: 2026-10-07 19:16

更新: 2026-10-07 19:16

形式化题目

给定 nn 个位置上的正整数 a1,a2,…,ana_1, a_2, \dots, a_n,每个 ai∈[1,109]a_i \in [1, 10^9]。 输入先给出 ss 条已知信息 api=dia_{p_i} = d_i(pip_i 严格递增), 再给出 mm 条区间信息,第 jj 条为 (lj,rj,kj,x1,…,xkj)(l_j, r_j, k_j, x_1, \dots, x_{k_j}), 其中 1≤lj<rj≤n1 \le l_j < r_j \le n、1≤kj≤rj−lj1 \le k_j \le r_j - l_j、 lj≤x1<x2<⋯<xkj≤rjl_j \le x_1 < x_2 < \cdots < x_{k_j} \le r_j。它的含义是

axt>ay对一切 t∈[1,kj] 和一切 y∈[lj,rj]∖{x1,…,xkj}. a_{x_t} > a_y \qquad \text{对一切 } t \in [1, k_j] \ \text{和一切 } y \in [l_j, r_j] \setminus \{x_1, \dots, x_{k_j}\}.

也就是说:区间 [lj,rj][l_j, r_j] 里被点名的这 kjk_j 个数,每个都严格大于剩下的 rj−lj+1−kjr_j - l_j + 1 - k_j 个数。 题目要求构造任意一组满足全部条件的 aa;无解则输出 NIE,有解则先输出 TAK, 再输出 nn 个正整数。

数据范围:1≤s≤n≤1051 \le s \le n \le 10^5,1≤m≤2×1051 \le m \le 2 \times 10^5,∑k≤3×105\sum k \le 3 \times 10^5。

因为所有 aia_i 都是整数,“严格大于"等价于"至少大 11”,于是每条信息都是 axt≥ay+1a_{x_t} \ge a_y + 1 形式的线性不等式——这正是差分约束的形状。

正解

思路

第一步:把所有不等式统一成"下界"

给每个位置维护一个下界 viv_i:初始 vi=1v_i = 1,已知位置直接取 vp=dv_{p} = d。 把每条不等式 au≥av+wa_u \ge a_v + w 记成一条有向边 v→uv \to u 权 ww, 含义是"uu 的下界至少要达到 vv 的下界加上 ww"。 按拓扑序把所有边推一遍

vu⟵max⁡(vu, vv+w), v_u \longleftarrow \max\bigl(v_u,\ v_v + w\bigr),

得到的 vv 就是每个位置被约束逼出来的最小取值。

第二步:一条信息要连多少边

最直接的翻译是:kk 个 xx 中的每一个都大于剩下的 r−l+1−kr-l+1-k 个位置, 于是要连 k (r−l+1−k)k\,(r-l+1-k) 条边。最坏 105×10510^5 \times 10^5,直接爆炸。

引入一个辅助点 pp 表示"XX 中的最小值",就能把"两两之间"压成"两次":

  • 每个剩下的位置 yy 连 y→py \to p 权 11,即 p≥ay+1p \ge a_y + 1(pp 严格大于它们);
  • pp 连 p→xtp \to x_t 权 00,即 axt≥pa_{x_t} \ge p。

传递一下就是 axt≥p>aya_{x_t} \ge p > a_y,恰好是要求。 边数从 k(r−l+1−k)k(r-l+1-k) 降到 r−l+1r-l+1。但一条 l=1, r=105, k=1l=1,\ r=10^5,\ k=1 的信息仍有 10510^5 条边, mm 条就是 2×10102 \times 10^{10} 条,还是不行。

第三步:用线段树压缩"剩下的位置"

区间 [l,r][l, r] 挖掉 kk 个点名的位置后,剩下的部分恰好是 k+1k+1 段连续空隙。 对位置建一棵线段树,先把"儿子 →\to 父亲、权 00"的边连好—— 这样父亲的值天然就是它所辖区间内所有位置下界的最大值。 于是一段空隙 [L,R][L, R] 只要拆成 O(log⁡n)O(\log n) 个线段树节点, 每个节点往 pp 连一条权 11 的边,就不必逐个位置连边了。

以题面样例的第二条信息 (l,r,k)=(4,5,1,{4})(l,r,k)=(4,5,1,\{4\}) 为例,空隙只有 {5}\{5\}:

flowchart LR
    L5["叶子 5<br/>a=3"] --"1"--> P2["条件点 p₂<br/>= min{a₄}"]
    P2 --"0"--> L4["叶子 4<br/>a≥4"]

读作 a4≥p2≥a5+1=4a_4 \ge p_2 \ge a_5 + 1 = 4。第一条信息 (1,4,2,{2,3})(1,4,2,\{2,3\}) 的空隙是 {1}\{1\} 和 {4}\{4\},两个叶子分别连一条权 11 边到 p1p_1,p1p_1 再连回叶子 2,32,3。

第四步:无解怎么判

推完之后只可能有三种矛盾:

  1. 约束成环:拓扑排序没能剥掉所有点。线段树内部(儿子 →\to 父亲)本身无环, 所以任何环都至少经过一个条件点,而进入条件点的边权全是 11, 环上权和 ≥1\ge 1,即"$a \ge a + $ 正数",矛盾。
  2. 下界越界:某个位置的下界 >109> 10^9,超出值域。
  3. 与已知值冲突:某个已知位置被推到的下界 >d> d,和 ap=da_p = d 冲突。

三种情况任一出即 NIE;都不出现时,令 ai=via_i = v_i 就是一组合法解。

为什么 ai=via_i = v_i 一定合法

设最终下界为 vv。

  • vi≤aiv_i \le a_i(对任意合法解):沿拓扑序归纳。源点 v=1≤av = 1 \le a; 已知位置 v=d=av = d = a;对每条边 v→uv \to u 权 ww,对应不等式 au≥av+w≥vv+wa_u \ge a_v + w \ge v_v + w,所以推完仍满足 vu≤auv_u \le a_u。
  • ai=via_i = v_i 满足每条信息:对空隙里的任意位置 yy,设覆盖它的那个线段树节点为 ss。 从叶子 yy 到 ss 全是权 00 的父子边,故 vs≥vyv_s \ge v_y;而 s→ps \to p 权 11, 于是 vp≥vy+1>vyv_p \ge v_y + 1 > v_y;又 p→xtp \to x_t 权 00 给出 vxt≥vpv_{x_t} \ge v_p, 合起来 vxt>vyv_{x_t} > v_y。
  • 已知位置取值精确:检查 3 通过时 vp=dv_p = d(初值就是 dd,且从未被推高)。

所以三种检查全部通过   ⟺  \iff 有解,算法是完备的。

实现细节:边权可以不存

图上的边权只有 00 和 11,而且恰好由终点类型决定:

边的来源 终点 权
儿子 →\to 父亲 线段树节点 00
空隙节点 →p\to p 条件点 11
p→xtp \to x_t 线段树叶子 00

即:线段树节点只有权 00 的入边,条件点只有权 11 的入边。 代码据此省掉一份边权数组,把最坏数据(≈6×106\approx 6 \times 10^6 条边)的常驻内存 压进 128128 MB。

代码

Python 短解法(与 C++ 同阶:同一张图、同一次拓扑排序):

python
#!/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++ 正式解:

cpp
/**
 * 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;
}

复杂度

设 Σk=∑jkj\Sigma k = \sum_j k_j。

  • 点数:O(n+m)O(n + m)(线段树 2n2n 量级 + 每条信息一个条件点)。
  • 边数:线段树 O(n)O(n) 条 + p→xtp \to x_t 共 Σk\Sigma k 条 + 每段空隙 O(log⁡n)O(\log n) 条, 空隙总数为 Σk+m\Sigma k + m,故总计 O(n+Σk+(Σk+m)log⁡n)O\bigl(n + \Sigma k + (\Sigma k + m)\log n\bigr)。
  • 时间:建图与拓扑排序都是每条边 O(1)O(1),即同阶 O(n+Σk+(Σk+m)log⁡n)O\bigl(n + \Sigma k + (\Sigma k + m)\log n\bigr)。
  • 空间:同阶,即图的规模本身。

代入上限 n≤105n \le 10^5、m≤2×105m \le 2\times 10^5、Σk≤3×105\Sigma k \le 3 \times 10^5, 边数在 10710^7 以内。

总结

这道题的骨架是"差分约束 + 拓扑排序",真正的难点在建图:

  1. 先把"严格大于"化成"≥\ge 加 11",把构造问题变成"求每个位置的下界"。
  2. 用一个辅助点代表集合最小值,把 k×(r−l+1−k)k \times (r-l+1-k) 条边压成 k+(r−l+1−k)k + (r-l+1-k) 条。
  3. 再用线段树把区间连边,把"逐个位置连边"压成 O(log⁡n)O(\log n) 条。 这是"线段树优化建图"的教科书用法:点 →\to 区间的边用"儿子 →\to 父亲"的 向上边汇聚,区间 →\to 点的边用线段树分解。
  4. 无解判定要凑齐三条:成环 / 越界 / 与已知值冲突。第三条最容易漏—— 只知道 ap=da_p = d 并不等于"vp=dv_p = d",还要检查它没有被其他约束推高。

关于本题的数据与样例,有两点需要如实说明:

  • 素材源里带有数据生成脚本(data.py),说明 data/ 是自造数据, 题面本身也可能是网络重建的,与官方原题(洛谷 P3588 [POI2015] Pustynia)的 细节可能有偏差;本题解按题面文字自行推导,未依赖任何外部题解。
  • 题面样例给出的输出是 6 7 1000000000 6 3,而本解输出 1 7 5 4 3。 两者都合法(读者可逐条核对上面两条信息),差别只在于本解取的是每个位置的最小可行下界, 而样例来自另一种构造。本题是"构造任意一组解",多解均判正确。 另经核对:本解与素材源的 std.cpp 在全部 1010 个数据点上输出逐字节一致, 且与 data/*.out 完全一致。