CF1951F.Inversion Composition

My Chemical Romance - Disenchanted

ඞ

给定一个长度为 $n$ 的排列 $p$，以及一个非负整数 $k$。你需要构造一个长度为 $n$ 的排列 $q$，使得 $\operatorname{inv}(q) + \operatorname{inv}(q \cdot p) = k {}^\dagger {}^\ddagger$，或者判断是否无法做到。

${}^\dagger$ 对于两个长度为 $n$ 的排列 $p$ 和 $q$，排列 $w = q \cdot p$ 满足 $w_i = q_{p_i}$，对于所有 $1 \le i \le n$。

${}^\ddagger$ 对于长度为 $n$ 的排列 $p$，函数 $\operatorname{inv}(p)$ 表示 $p$ 的逆序对数，即满足 $1 \le i < j \le n$ 且 $p_i > p_j$ 的数对 $(i, j)$ 的数量。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 3 \cdot 10^5, 0 \le k \le n(n - 1)$），分别表示排列 $p$ 的长度和目标逆序对数。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，$p_i$ 两两不同），表示给定的排列 $p$。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试用例，如果存在满足条件的排列 $q$，输出一行 "YES"。否则输出一行 "NO"。

如果答案为 "YES"，则在下一行输出 $n$ 个整数 $q_1, q_2, \ldots, q_n$，表示满足条件的排列 $q$。如果有多种方案，输出任意一种即可。

在第一个测试用例中，有 $q \cdot p = [2, 1, 3]$，$\operatorname{inv}(q) = 3$，$\operatorname{inv}(q \cdot p) = 1$。

在第四个测试用例中，有 $q \cdot p = [9, 1, 8, 5, 7, 6, 4, 3, 2]$，$\operatorname{inv}(q) = 24$，$\operatorname{inv}(q \cdot p) = 27$。

由 ChatGPT 4.1 翻译