题解

题意简述

给定排列 $a$ 和部分确定的排列 $c$（$0$ 表示未知），要求构造一个排列 $b$，满足：

1. $b$ 与 $c$ 一致（$c_i \neq 0$ 时 $b_i = c_i$）；
2. $b$ 是“好的”，即存在一系列题目所述操作（选择区间 $[l,r]$ 满足 $a_r = \min(a_l,\dots,a_r)$，并将该区间向右循环移位一次），使得 $a$ 可以变为 $b$。

若可能则输出 $b$，否则输出 $-1$。

思路分析

1. 好排列的充要条件

关键观察：
操作的本质：选择 $l,r$ 且 $a_r = \min(a_l,\dots,a_r)$，将 $a_r$ 移动到 $a_l$ 的位置，其他元素右移一位。
这个操作不会将原本 $a$ 中的顺序对 $i<j$ 变成逆序对（即如果 $i$ 在 $a$ 中出现在 $j$ 之前，那么操作后 $i$ 仍在 $j$ 之前，或者可能 $j$ 移动到 $i$ 前面？需要更严谨）。

实际上，该操作对于值的大小关系保持如下性质：

• 若 $x<y$ 且在 $a$ 中 $x$ 出现在 $y$ 之前，那么在任何可达的排列中，$x$ 仍出现在 $y$ 之前。

证明：每次操作将区间的最小值 $a_r$ 移到最左端，它不会越过比它大的元素，也不会被比它小的元素越过（因为它是最小值）。因此，任意两个数之间的相对顺序（按原 $a$ 中的位置关系）不会改变，除非它们相等（不可能）。

因此，$b$ 是好的当且仅当对于任意 $x<y$，若 $x$ 在 $a$ 中的位置 < $y$ 在 $a$ 中的位置，则 $x$ 在 $b$ 中的位置 < $y$ 在 $b$ 中的位置。

即 $a$ 与 $b$ 之间的值顺序关系保持一致（$a$ 给出了一个值的偏序，$b$ 必须线性扩展这个偏序）。

2. 转化为区间限制

设 $p[x]$ 为 $x$ 在 $a$ 中的位置，$q[x]$ 为 $x$ 在 $b$ 中的位置（若 $c$ 已知则 $q[x]=c$ 中该值的位置，否则未知）。
条件等价于：对所有 $x<y$，如果 $p[x] < p[y]$，则必须 $q[x] < q[y]$。

这类似于：将值 $1..n$ 按照 $p$ 的顺序排成一列，则 $q$ 必须保持这个顺序（即 $q$ 是 $p$ 的一个线性扩展）。
换句话说，如果我们按 $p[x]$ 递增的顺序考虑 $x$，则 $q[x]$ 也必须递增。

于是问题变为：已知某些 $q[x]$ 的值，其他未知，要求 $q$ 严格递增（按 $p[x]$ 顺序）且 $1..n$ 每个位置恰好一个值。

3. 检查已知约束

我们按 $p[x]$ 递增的顺序遍历 $x$，维护当前已填的 $q$ 的最大值。
若遇到已知 $q[x]$，它必须大于之前所有已知 $q$，否则无解。

设 $L[x]$ 和 $R[x]$ 为 $x$ 在 $b$ 中可能的位置范围：

• $L[x]$：由于所有小于 $x$ 且 $p[y]<p[x]$ 的值必须排在 $x$ 之前，$x$ 的位置至少是这些值的数量 $+1$。这可以通过对 $p$ 顺序做前缀计数得到。
• $R[x]$：由于所有大于 $x$ 且 $p[y]>p[x]$ 的值必须排在 $x$ 之后，$x$ 的位置至多是 $n$ 减去这些值的数量。也可通过后缀计算。

实际上标程用两个树状数组求 $L[x]$ 和 $R[x]$：

• 从左到右扫描 $i$（按 $a$ 的位置），遇到已知 $q[a[i]]$ 则更新树状数组记录最大值，遇到未知则 $c[i]=$ 当前最大值 $+1$ 作为左界。
• 从右到左扫描，类似得到右界。若左界 > 右界则无解。

4. 贪心填充未知位置

现在问题变成：有 $m = n - \#\{\text{已知}\}$ 个未知值，每个未知值 $x$ 有一个可选位置区间 $[L_x, R_x]$，且这些区间满足单调性（因为按 $p$ 顺序 $L,R$ 均递增）。
我们要给每个未知值分配一个位置，使得：

• 位置互不相同；
• 每个位置 $i$（$1..n$）上最多一个值；
• 已知值已固定在 $c$ 中，不能与未知冲突。

经典贪心：按位置 $i=1..n$ 依次考虑，维护一个优先队列，存放所有左界 $\le i$ 的未知值，按右界从小到大排序。
对于位置 $i$，如果 $c[i]$ 已知，则直接填；否则从优先队列中取出右界最小的（即最紧迫的）赋值给 $b[i]$，若其右界 $< i$ 则无解。

由于区间单调，每次加入的新值左界递增，且右界也递增，因此贪心正确。

5. 实现细节

• 用两个树状数组：一个维护前缀最大值（求 $L$），一个维护后缀最小值（求 $R$）。
• 将未知值按 $L$ 分组存入 vc[L]。
• 遍历位置 $i$，先将所有 $L = i$ 的未知值加入优先队列（按 $R$ 小优先）。
• 若 $c[i]$ 已知，直接跳过；否则从队列中取出 $R$ 最小的赋值，若 $R < i$ 则无解。
• 输出 $b$。

复杂度

• 树状数组操作 $O(\log n)$。
• 每个未知值入队出队一次，$O(\log n)$。
• 总复杂度 $O(n \log n)$，$n$ 总和 $5\times 10^5$，可行。

代码

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

const int maxn = 500100;

int n, a[maxn], b[maxn], c[maxn], p[maxn], q[maxn];

struct node {
    int r, x;
    node(int a = 0, int b = 0) : r(a), x(b) {}
    bool operator < (const node &o) const {
        return r > o.r || (r == o.r && x > o.x);
    }
};

vector<node> vc[maxn];

struct DS1 { // 前缀最大值
    int c[maxn];
    void init() { for (int i=0;i<=n;++i) c[i]=0; }
    void upd(int x,int d) { for(;x<=n;x+=x&-x) c[x]=max(c[x],d); }
    int qry(int x) { int r=0; for(;x;x-=x&-x) r=max(r,c[x]); return r; }
} T1;

struct DS2 { // 后缀最小值
    int c[maxn];
    void init() { for (int i=0;i<=n;++i) c[i]=n+1; }
    void upd(int x,int d) { for(;x;x-=x&-x) c[x]=min(c[x],d); }
    int qry(int x) { int r=n+1; for(;x<=n;x+=x&-x) r=min(r,c[x]); return r; }
} T2;

void solve() {
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i], p[a[i]]=i, q[i]=0, vc[i].clear();
    for(int i=1;i<=n;++i) {
        cin>>b[i];
        if(b[i]) q[b[i]]=i;
    }
    // 检查已知顺序
    T1.init();
    for(int i=1;i<=n;++i) if(q[i]) {
        if(T1.qry(p[i])>q[i]) {cout<<"-1\n";return;}
        T1.upd(p[i],q[i]);
    }
    // 求左界
    T1.init(); T2.init();
    for(int i=1;i<=n;++i) {
        if(q[a[i]]) T1.upd(a[i],q[a[i]]);
        else c[i]=T1.qry(a[i])+1;
    }
    // 求右界
    for(int i=n;i>=1;--i) {
        if(q[a[i]]) T2.upd(a[i],q[a[i]]);
        else {
            int r=T2.qry(a[i])-1;
            if(c[i]>r) {cout<<"-1\n";return;}
            vc[c[i]].emplace_back(r,a[i]);
        }
    }
    // 贪心填未知
    priority_queue<node> pq;
    for(int i=1;i<=n;++i) {
        for(node u:vc[i]) pq.push(u);
        if(!b[i]) {
            if(pq.empty()||pq.top().r<i) {cout<<"-1\n";return;}
            b[i]=pq.top().x; pq.pop();
        }
    }
    for(int i=1;i<=n;++i) cout<<b[i]<<" \n"[i==n];
}

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