AT_tupc2024_a.Inversions of PQ and QP

给定 $3$ 个整数 $N, A, B$。

请判断是否存在 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\dots,P_N)$ 与 $Q=(Q_1,Q_2,\dots,Q_N)$，满足以下条件：

• 序列 $(P_{Q_1},P_{Q_2},\dots,P_{Q_N})$ 的逆序对数为 $A$；
• 序列 $(Q_{P_1},Q_{P_2},\dots,Q_{P_N})$ 的逆序对数为 $B$。

如果存在，构造出这样的一组 $P,Q$。

对于每组测试用例，请分别作答。

逆序对数指对于长度为 $M$ 的数列 $R=(R_1,R_2,\dots,R_M)$，满足 $1 \leq i < j \leq M$ 且 $R_i > R_j$ 的整数对 $(i, j)$ 的数量。

输入通过标准输入给出，格式如下：

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每组测试用例给出如下三个整数：

$N$ $A$ $B$

对于每组测试用例，按顺序输出答案。

如果存在满足条件的排列 $P=(P_1,P_2,\dots,P_N)$ 和 $Q=(Q_1,Q_2,\dots,Q_N)$，输出格式为：

Yes $P_1$ $P_2$ $\dots$ $P_N$ $Q_1$ $Q_2$ $\dots$ $Q_N$

否则输出：

No

如果存在多组解，输出任意一组均视为正确。

样例解释 1

对于第 $1$ 个输入用例，输出 $(P_{Q_1}, P_{Q_2}, P_{Q_3})=(3,2,1)$，$(Q_{P_1},Q_{P_2},Q_{P_3})=(2,1,3)$。

数据范围

• $1 \leq T \leq 2\times 10^5$
• $1 \leq N \leq 2\times 10^5$
• $0 \leq A \leq \frac{N(N-1)}{2}$
• $0 \leq B \leq \frac{N(N-1)}{2}$
• 所有输入均为整数
• 所有输入文件中，$N$ 的总和不超过 $2\times 10^5$

由 ChatGPT 5 翻译