题目
题意
给定长度为 $2N$ 的两个序列 $A$ 和 $B$。
构造一个长度为 $2N$ 的序列 $\mathrm{C}$。满足以下条件：
- 序列 $\mathrm{C}$ 的第 $i$ 个数 $C_i$，只能从 $A_i$ 和 $B_i$ 中选取。
- 设 $a$ 为序列 $\mathrm{A}$ 中元素被选取的次数，$b$ 为序列 $\mathrm{B}$ 中元素被选取的次数，则 $a = b = N$。
- 该序列是一个单调上升的序列，不要求严格单调上升。
如有多解，任意输出一组解即可。
题解
设 $f_{i, j, A/B}$ 表示当前从 $A$ 中选了 $i$ 个，从 $b$ 中选了 $j$ 个，最后一个是从 $A/B$ 中选的是否可行。
这时调换定义域和值域。$f_{i, 0/1, A/B}$ 表示 $\left\{j \mid f_{i, j, A/B} = 0/1\right\}$。由于 $f_{i, 0, A/B}$ 与 $f_{i, 1, A/B}$ 互为补集，不妨只考虑 $f_{i, 1, A/B}$。
转移为从某两个 $f$ 的并转移到 $f_{i, *, *}$，可能会加 $1$。由于原来的 $f$ 是连续的一段区间，所以之后的 $f$ 是前面的并，所以也是连续的区间。
我们在看回原来的状态，因为使得 $f_{i, j, A/B}$ 为 $1$ 的 $j$ 是一个连续段，所以此时可以将状态改为 $g_{i, A/B}$ 表示前 $i$ 位选定，最后一个选的是 $A/B$ 里的数，可行的 $j$ 的范围。
于是状态数 $\Theta\left(n\right)$，每次转移 $\Theta\left(1\right)$，总复杂度为 $\Theta\left(n\right)$。