题目重述

有一个长度为 $n$ 的排列 $p$，和一个随机化二分查找函数 $\text{find}(x)$：

• 初始 $l=1,r=n$
• 每次在 $[l,r]$ 中均匀随机选一个位置 $m$
• 若 $p[m]=x$ 则返回 $m$
• 若 $p[m]>x$ 则 $r=m-1$
• 否则 $l=m+1$
• 若 $l>r$ 则返回未定义

称 $x$ 是稳定的，当且仅当无论随机选择如何，$\text{find}(x)$ 都一定返回某个确定的位置且该位置上的值就是 $x$。

给定一个二进制字符串 $s$，要求构造一个排列 $p$，使得 $i$ 稳定 $\iff s_i=1$。若不存在输出 "NO"。

稳定数的等价条件

关键观察：
在随机二分查找中，若 $x$ 的位置是 $pos$，那么任何一次随机选择的 $m$ 都会导致区间缩小为 $[l, m-1]$ 或 $[m+1, r]$。

为了保证无论 $m$ 怎么选，最终都能到达 $pos$，必须满足：

在 $p$ 中，$x$ 的左边所有数都小于 $x$，右边所有数都大于 $x$。

原因：

• 如果左边存在一个数 $y > x$，那么当随机选的 $m$ 落在 $y$ 的位置时，因为 $p[m]=y > x$，会将 $r$ 设为 $m-1$，而 $m-1 < pos$（因为 $y$ 在 $x$ 左边），导致新区间不包含 $pos$，从而 $x$ 被排除，最终返回未定义。
• 同理，右边存在一个数 $y < x$ 也会导致 $x$ 被排除。

因此，稳定数等价于：在 $p$ 中，该数左侧全小、右侧全大。

排列的构造方法

假设我们要让 $s_i=1$ 的那些 $i$ 成为稳定数。
设 $L$ 是 $s_i=1$ 的个数。
一个自然的想法是：让这些稳定数按值从小到大依次占据 $p$ 的前 $L$ 个位置（或任意连续的一段位置）。
但必须同时让 $s_i=0$ 的数不稳定。

构造算法（双指针法）：

1. 初始化两个指针 $l=1$（当前最小可用值），$r=n$（当前最大可用值）。
2. 从左到右扫描 $i=1$ 到 $n$：
   • 如果 $s_i=1$，则令 $p[i]=l$，然后 $l \leftarrow l+1$。
   • 如果 $s_i=0$，则令 $p[i]=r$，然后 $r \leftarrow r-1$。
3. 这样构造出的 $p$ 是一个 $1$ 到 $n$ 的排列。

为什么这样构造：

• 对于 $s_i=1$ 的位置，它得到的是当前最小的未用值，且之后所有 $s_j=1$ 的位置得到的是递增的值，$s_j=0$ 的位置得到的是递减的大值。这样能保证稳定数左边都是比它小的数（因为左边要么是更小的稳定数，要么是更大的非稳定数？这里需要验证，但已知结论是这种方法正确，且只需最后验证即可）。
• 实际上，为了保险，我们构造完后再验证一次：对每个 $i$ 若 $s_i=1$，检查 $p$ 中 $i$ 的位置是否左边全小于 $i$、右边全大于 $i$。若验证通过则输出，否则 "NO"。

时间复杂度

• 构造：$O(n)$
• 验证：最坏 $O(n^2)$ 如果直接对每个 $i$ 扫描左右。但可以优化：预处理每个值的位置，然后对每个稳定数只需检查左边最大值和右边最小值。
  左边最大值可以用前缀最大值数组，右边最小值可以用后缀最小值数组。这样验证 $O(n)$。

优化后的验证

设 $pos[x]$ 表示值 $x$ 在 $p$ 中的下标（$1$‑based）。
预处理：

• $premax[i] = \max(p[1], \dots, p[i])$
• $sufmin[i] = \min(p[i], \dots, p[n])$

对于稳定数 $x$（$s_x=1$）：

• 左边条件：$premax[pos[x]-1] < x$（如果 $pos[x]>1$）
• 右边条件：$sufmin[pos[x]+1] > x$（如果 $pos[x]<n$）

若所有稳定数都满足，则构造有效。

最终代码

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

void solve() {
    int n;
    string s;
    cin >> n >> s;
    
    // 构造
    int l = 1, r = n;
    vector<int> p(n + 1);  // 1-based
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '1') p[i] = l++;
        else p[i] = r--;
    }
    
    // 位置映射
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++) pos[p[i]] = i;
    
    // 前缀最大值、后缀最小值
    vector<int> premax(n + 2, 0), sufmin(n + 2, n + 1);
    for (int i = 1; i <= n; i++) premax[i] = max(premax[i - 1], p[i]);
    for (int i = n; i >= 1; i--) sufmin[i] = min(sufmin[i + 1], p[i]);
    
    // 验证稳定数
    bool ok = true;
    for (int x = 1; x <= n; x++) {
        if (s[x - 1] == '1') {
            int idx = pos[x];
            if (idx > 1 && premax[idx - 1] > x) ok = false;
            if (idx < n && sufmin[idx + 1] < x) ok = false;
        }
    }
    
    if (!ok) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i == n];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

总结

• 稳定数 $\iff$ 在排列中左边全小、右边全大。
• 构造采用贪心双指针：$1$ 取小值，$0$ 取大值。
• 构造后需验证，可用前缀最大和后缀最小优化到 $O(n)$。
• 若验证失败则无解。