题目题解

问题理解

给定数组 $x$（$1 \le x_i \le i$），要求判断是否存在一个排列 $a$，使得对每个前缀 $[a_1, \dots, a_i]$，其 $f$ 值等于 $x_i$。
其中 $f(a)$ 定义为：将 $a$ 划分成若干子数组，取每个子数组的最小值构成数组 $b$，在所有划分中选择使得 $b$ 字典序最大的 $k$（子数组个数）。

---

第一步：已知排列求 $f$

先考虑逆问题：给定排列 $p$，如何计算 $f(p)$？

结论：
设 $p_1$ 为第一个元素。找到最小的 $i > 1$ 使得 $p_i < p_1$。

• 若不存在这样的 $i$，则 $f(p) = 1$（整个数组作为一个子数组）。
• 否则，找到 $j \in [1, i]$ 使得 $p_j$ 是 $[1, i]$ 中的最大值，则第一个子数组取 $[p_1, \dots, p_{j-1}]$，然后递归处理剩余部分。

这样得到的 $k$ 即为 $f(p)$。

---

第二步：转化为树结构

将 $x$ 视为每个前缀的 $f$ 值。
设 $j$ 是最大的索引 $j < i$ 使得 $x_j = x_i - 1$。
则 $j$ 可以看作是 $i$ 的“父节点”，形成一棵树（根为 $1$，因为 $x_1 = 1$ 固定）。

必要条件：

1. $x_1$ 必须为 $1$（否则无解）。
2. 对每个 $i$，$x_i - x_{i-1} \le 1$（因为 $f$ 每次最多增加 $1$）。
3. 若 $x_i = x_{i-1}$，则 $i$ 与 $i-1$ 在树中为兄弟关系。
4. 若 $x_i = x_{i-1} + 1$，则 $i$ 是 $i-1$ 的第一个孩子（或更深）。
5. 若 $x_i < x_{i-1}$，则 $i$ 是某个祖先的新孩子。

---

第三步：树的性质与构造

设节点 $i$ 的值为 $v = x_i$。
考虑节点 $i$ 的子树：它包含所有 $x_j \ge v$ 且 $j$ 在 $i$ 之后的连续段，直到遇到 $x_j = v-1$ 为止。

关键观察（对应 $[1,2,2,3,3]$ 无解的原因）：
如果某个节点有多个孩子，那么这些孩子只能有最多一个孩子（即不能有孙子），否则会产生矛盾。

因此，树的结构必须满足：

• 每个节点最多有一个“长链”孩子（即该孩子还有孩子），其余孩子必须是叶子（无孩子）。

---

第四步：递归构造排列

我们按树的结构递归分配数字 $1 \dots n$ 给节点。

设当前处理的子树对应区间 $[l, r]$，需要填入的数字范围为 $[L, R]$，且节点 $l$ 的值已经确定。

1. 找到节点 $l$ 的所有直接孩子（即满足 $x_k = x_l + 1$ 且 $k > l$ 且 $k$ 在 $l$ 的子树内）。
2. 如果孩子数量 $> 1$：
   • 每个孩子只能有最多一个孩子（否则无解）。
   • 将剩余数字从大到小分配给这些孩子（让每个孩子得到该子树中的最大值）。
   • 递归处理每个孩子的子树。
3. 如果只有一个孩子：
   • 根据上下文决定该孩子是取最大值还是最小值（取决于它是否可能成为链的一部分）。

根节点 $1$ 的处理：

• 如果 $x$ 中 $2$ 的个数 $> 1$，则 $p_1 = 1$（最小），否则 $p_1 = n$（最大）。

---

第五步：算法步骤

1. 检查 $x_1$ 是否为 $1$，以及 $x_i - x_{i-1} \le 1$ 是否成立。
2. 构建逆映射 inv[v] 存储所有值为 $v$ 的位置（按索引顺序）。
3. 从根开始递归构造：
   • 使用栈模拟递归，避免深度过大。
   • 分配数字时维护左右边界。
4. 若构造过程中出现矛盾（如孩子数不符合条件），则输出 "NO"，否则输出构造的排列。

---

时间复杂度

• 每个节点处理一次，总复杂度 $O(n)$。
• 满足 $\sum n \le 2\times 10^5$。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<int> solve(const vector<int>& b, vector<vector<int>>& inv) {
    int n = b.size();
    if (inv[1].size() > 1) return {};
    
    vector<int> a(n);
    stack<array<int, 5>> st;
    
    if (inv[2].size() > 1) {
        a[0] = 1;
        st.push({0, n - 1, 2, n, 1});
    } else {
        a[0] = n;
        st.push({0, n - 1, 1, n - 1, 1});
    }
    
    while (!st.empty()) {
        auto [l, r, leftNum, rightNum, ok] = st.top();
        st.pop();
        if (l == r) continue;
        if (b[l + 1] != b[l] + 1) return {};
        int num = b[l] + 1;
        if (num >= (int)inv.size()) return {};
        
        vector<int> nxt;
        while (!inv[num].empty() && inv[num].back() > l) {
            nxt.push_back(inv[num].back());
            inv[num].pop_back();
        }
        if (nxt.empty()) return {};
        if (!ok && nxt.size() != 1) return {};
        
        if (nxt.size() == 1) {
            if (num + 1 < (int)inv.size() && inv[num + 1].size() > 1 && inv[num + 1][inv[num + 1].size() - 2] > l) {
                a[nxt[0]] = leftNum++;
            } else {
                a[nxt[0]] = rightNum--;
            }
            st.push({l + 1, r, leftNum, rightNum, 1});
        } else {
            rightNum -= nxt.size();
            int nx = rightNum + 1;
            reverse(nxt.begin(), nxt.end());
            int curLeft = leftNum;
            for (int i = 0; i < (int)nxt.size(); ++i) {
                int pos = nxt[i];
                a[pos] = nx++;
                int nextInd = (i + 1 < (int)nxt.size() ? nxt[i + 1] - 1 : r);
                int sz = nextInd - pos - 1;
                st.push({pos, nextInd, curLeft, curLeft + sz, 0});
                curLeft += sz + 1;
            }
        }
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> x(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        
        // 快速检查不可能情况
        if (x[0] != 1) {
            cout << "NO\n";
            continue;
        }
        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (x[i] - x[i - 1] > 1) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            cout << "NO\n";
            continue;
        }
        
        vector<vector<int>> inv(n + 3);
        for (int i = 0; i < n; i++) {
            inv[x[i]].push_back(i);
        }
        
        auto a = solve(x, inv);
        if (a.empty()) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
            for (int v : a) cout << v << ' ';
            cout << '\n';
        }
    }
    return 0;
}

---

验证样例

输入：

8
3
1 2 2
2
1 1
3
1 2 1
3
1 2 3
4
1 2 2 4
4
1 2 3 3
5
1 2 3 2 3
9
1 2 3 4 5 4 5 6 6

输出：

YES
1 2 3
NO
NO
YES
3 1 2
NO
YES
3 1 2 4
YES
1 4 3 5 2
YES
5 2 1 8 6 9 3 4 7

与题目输出一致。

---

总结

本题的关键在于：

1. 将 $f$ 值的序列转化为树的深度结构。
2. 识别出树结构的限制（多孩子节点只能有叶子孩子）。
3. 通过递归分配数字构造排列。