题目大意
给定一个长度为 $n$ 的排列。
现在有两个空数组 $X$ 和 $Y$，你要依次把排列的每个元素放到 $X$ 数组或者 $Y$ 数组，使得最后 $X$ 数组和 $Y$ 数组的 high element 个数相同。定义数组中一个元素为 high element 当且仅当它是其前缀最大值。
一个元素放 $X$ 数组记为 $0$，放 $Y$ 数组记为 $1$，你要求字典序最小的方案，或输出无解。
$n \leq 2 \times 10^5$
题解
（看题解学的思路，这里差不多就是把题解翻译了一遍。。。
首先大的框架肯定是贪心，贪心考虑每一位能不能放 $X$，不行的话能不能放 $Y$。
所以问题相当于，现在 $X$ 数组里最大值为 $h_X$，high element 数量为 $c_X$，$Y$ 数组里最大值为 $h_Y$，high element 数量为 $c_Y$，排列里剩下的元素是否存在分配方案使得最后 $c_X=c_Y$。
然后需要观察两条性质：
1、原排列里的 high element 分配到数组里以后仍然是 high element。（很显然)
2、假设成功分配的话最后各数组的 high element 长这样：
- $h_X < a_1 < a_2 < \cdots a_x$
- $h_Y < b_1 < b_2 < \cdots b_y$
- 满足 $c_X+x=c_Y+y$
那么必然存在一种分配方案，使得 $a_1,\cdots,a_x$ 全是原排列的 high element，或使得 $b_1,\cdots,b_y$ 全是原排列的 high element。
（证明：不然的话，$a_1,\cdots,a_x$ 中存在一项不是原排列的 high element，那把它丢到 $Y$ 数组去它就不产生贡献了，同理也把 $b$ 中的一个非原排列 high element 项丢到 $X$ 去。这样不会破坏 $c_X+x=c_Y+y$ 这条性质。）
于是首先假设 $a_1,\cdots,a_x$ 全是原排列的 high element（反过来同理）。那么我们只需要考虑 $b_1,\cdots,b_y$ 怎么选，选好之后剩下的 high element 丢给 $X$ 组成 $a_1,\cdots,a_x$，剩下的非 high element 在哪边不产生贡献就留在哪边，即可。
设排列（当前剩余部分）有 $Q$ 个元素是原来的 high element，那么我们需要选择 $b_1,\cdots,b_y$ 使得 $c_X+Q-k=c_Y+y$，其中 $k$ 表示 $b_1,\cdots,b_y$ 中的原排列 high element 的数量。
移项得 $c_X-c_Y+Q=y+k=2k+(y-k)$。而等式左边是个定值。这相当于，我从剩余的排列中选一个上升子序列，其中如果这个元素是原排列的 high element 就得 2 分，否则得 1 分，问能否凑出 $c_X-c_Y+Q$ 分。
再观察发现，如果我有选 1 分元素，所能获得的最大得分是 $m$，那么 $[0,m]$ 这个区间的得分都是可以达到的。如果我只选了 2 分元素，能获得的最大得分是 $m$，那么 $[0,m]$ 这个区间的偶数得分也都是可以达到的。
因此只需要求最大得分就行了。这是个类似 LIS 的 dp，设 $f_{i,0/1}$ 表示从排列的第 $i$ 项开始，不选 / 选过 1 分元素所能获得的最大得分。
把这个 dp 值保存在线段树上（$f_{i}$ 的值保存在 $p_i$ 的位置），这样就一边贪心一边询问了，时间复杂度 $O(n \log n)$。
代码
// 自从学了日语，变量名都开始用日语了。。人家日语题面就是“高い項”嘛肯定是用 takai 啦
1 |
|