【解题报告】IOI2020
属于是很多讲课里都讲到过的一场 但是我几乎没有记住的。
Day 1
$\text{plants}$
首先，根据部分分的提示，思考 $2k>n$ 的部分分做法。考虑当前的全局最大值 $x$，一个必要条件是 $r_x=0$，因为没有比最大值更大的点。而如果还存在一个 $y$ 使得 $r_y=0$，应该如何判断 $x,y$ 的大小关系呢？由于 $2k>n$，所以 “$x$ 的区间覆盖 $y$” 和 “$y$ 的区间覆盖 $x$” 两者至少满足一项。如果 $x$ 的区间覆盖了 $y$，而 $r_x$ 仍然为 $0$，说明 $x$ 处元素 $>$ $y$ 处元素。（实际上两者也恰好有一个成立）
通过这种方式，我们就可以得到全局最大值的位置：计算每一个 $r_x=0$ 的 $x$ 和 $x$ 之前最近的满足 $r_y=0$ 的 $y$ 的距离，取这个距离最大的 $x$，即为全局 $\max$。然后，我们相当于要删除 $x$ 处元素，只需要将区间覆盖到 $x$、且还没遍历到过的点的 $r$ 减 $1$ 即可。
这个过程明显可以通过线段树 $+$ set 来做到 $\mathcal{O}(n\log n)$。实际上，直接实现这个可以获得 $\text{44pts}$，因为 “满足返回值一定是 $1$ 或 $-1$” 这个 $\text{subtask}$ 也是这么做的：因为我们求出了一组合法的排列，而返回值不存在 $0$ 说明 “任意一组合法解，即可代表所有合法解”。
如何把他改对？注意到每次我们实际上只关注了每连续 $k$ 个元素的相对大小，所以在做上面过程的时候，我们将钦定当前位置的值，改成将其与覆盖他的点之间连边（$a_x<a_y$ 则 $x\to y$），然后传递闭包，即可在 $\mathcal{O}(n^3)$ 的时间内解决问题。
但正解明显不能显式地建立 $\text{DAG}$，所以我们需要一个更厉害的条件。注意到若 $x,y$ 之间的距离 $< k$，则我们可以直接通过比较钦定他们的值的大小关系，来比较他们的实际大小。于是，如果要比较的 $x,y$ 之间距离过大，一个方法是构造一条不等式链，例如 $a_x>a_{p_1}>a_{p_2}\cdots >a_{p_k}>a_y$。因此，一个想法是对于 $x$，每次不断往 $(x-k,x+k)$ 区间中的某一个点跳，满足 $a_x>a_{x'}$，然后继续拓展，拓展到 $x'$ 的区间包含 $y$，若 $a_{x'}\ge a_y$，则说明 $a_x>a_y$。
如何优化？注意到在 $(x,x+k)$ 中，我们跳到的点的值应该 $<$ $x$ 处的值，所以，如果我们一次性就跳到了一个很小的点上，这明显是不优的。因此，我们只把 $x$ 的出边设为 “比 $a_x$ 小的最大元素” 的位置，一直这么跳过去，一定是 “损耗” 尽量少的。而且由于每次跳的距离不会越过 $k$，所以一定有一个时刻，$x'$ 的区间覆盖 $y$，从而得以直接比较大小。
当然，要向左、向右分别连边，由于向一边的出边只有至多一条，所以可以倍增优化。如果通过这种方式，不能判断 $a_x>a_y$ 或 $a_y>a_x$，则说明是不可确定的。时间复杂度 $\mathcal{O}(n\log n)$。
$\text{supertrees}$
首先，由于 $p_{i,j}=0$ 说明他们不在一个连通块内，划分成多个连通块分别做。
由于 $p_{i,j}\le 3$，所以任意连通块中至多只有一个环（否则一定有两个点之间路径条数 $\ge 4$）。
如果一个连通块内路径条数均为 $1$，则直接建一棵树即可；
若连通块内路径条数存在 $2$，则一定要用到一个环，把 $p_{i,j}=1$ 的部分连成树，然后每棵树上拿一个点出来，造一个环即可（需要特判环节点个数 $\le 2$ 的情况，即无解）。
再考虑存在路径条数为 $3$ 的部分。注意到一个环至多为两个点之间贡献 $1$ 条新路径，所以 $3$ 条路径至少要两个环，直接无解。
$\text{tickets}$
由于 $n$ 是偶数，所以选出来的数中较大的 $\dfrac{n}{2}$ 系数取正；较小的 $\dfrac{n}{2}$ 系数取负。
对于一种颜色的奖券，取负号的一定是一段前缀，取正号的一定是一段后缀，这样才是最优的，当然，一共需要有恰好 $k$ 个被选中。
假设现在我们得到了一组解，如何构造 $k$ 次各自的方案呢？一个简单的想法是每次选出 $k$ 个，然后归纳成 $k-1$ 的情况。能选出一组当且仅当：
存在一种方法，从 $\dfrac{n}{2}$ 种颜色中选出取正号的元素，从另外 $\dfrac{n}{2}$ 种颜色中选出取符号的元素。同时所有取负号的元素 $\le$ 所有取正号的元素。
能选出正号、负号各一半，只需要“全正”的颜色个数 $\le \dfrac{n}{2}$，“全负”的颜色个数 $\le \dfrac{n}{2}$ 即可。这显然成立，因为如果某一种的个数 $>\dfrac{n}{2}$，则取这种符号的元素个数 $>$ 需要的个数，显然不可能。
再考虑取负号的全部 $\le$ 取正号的，这个条件。注意到如果 $x>y$，但 $x$ 取负号，$y$ 取正号，则交换 $x,y$ 的符号之后答案更优。于是，如果这个条件不满足，我们便找到了一个更优的方案。
这同样说明，当我们已经找到了最优的方案，就不会出现上述情形。这恰好与我们的目的契合。
现在的问题变成如何找到最优答案。不妨首先钦定每种颜色都选 $k$ 个正号，则此时有 $nk$ 个正号，$0$ 个负号。每次选择一个使答案 $\Delta$ 最小的颜色，去掉一个正号、加入一个负号。显然这个贡献是有凸性的，即可以直接用堆贪心地选择，得到的即最优解。
而且由于本题的贪心次数是固定的，所以甚至可以把 priority_queue 改成 nth_element，连 $\log$ 都吃掉了。
Day 2
$\text{biscuits}$
考虑在确定了一个 $y$ 的时候，怎么判断他是否合法。比较显然的想法是从高位往低位构造，尽量填满。因为低位可以凑出高位，但是高位不能凑出低位。
或者说，如果设 $\text{sum}_i$ 是 $0$ 到 $i$ 位上元素的总和，$y$ 合法的必要条件是：
$$ \forall i,\ y\bmod {(2^{i+1}-1)}\le \dfrac{\text{sum}_i}{x} $$
因为高位拼不出低位，所以更低的位置要自给自足。注意到这也是充分条件了。因为可以从低位开始，逐步拼好当前的位，将低位元素两两拼成一个更高位的元素。
因此，只要一个 $y$ 满足上述条件，他就是合法的。于是考虑数位 $\text{dp}$，设 $\text{dp}_{i,j}$ 表示从高位往低位填到第 $i$ 位，更高位的限制中最紧的是 $\text{sum}_j$ 处的限制（如果没有则 $j=-1$）的方案数。则每次只需要枚举 $y$ 这一位放什么，然后更新更紧的限制即可，时间复杂度 $\mathcal{O}(k^2)$。
$\text{mushrooms}$
首先，求出每个位置的颜色是不可能的。因此，考虑什么样的形式可以一次性得到一堆下标中的 $A$ 的个数。发现 A?A?A?A?A? 这种就可以计算出 ? 中恰好有多少个 $A$，这是因为如果一个位置是 $B$，就会与左右的 $A$ 各产生一个贡献，否则就没有贡献。
考虑分块，我们首先求出 $S$ 个 $A$ 或 $S$ 个 $B$ 的位置，然后 $S$ 个 $S$ 个地确定后面的元素中 $A$ 的个数。求出 $S$ 个 $A$ 或 $S$ 个 $B$，如果每次暴力和第一个位置问，总步数就是 $\mathcal{O}(3\sqrt{n})$ 级别，因为可以尽量把前缀中 $A,B$ 的个数变得平衡，其中一个达到 $S$ 个就需要 $2S$ 次操作。这样能拿到大概 $\text{57pts}$。
根据部分分的提示，考虑如何在 $1$ 次操作内问出 $2$ 个位置的确切值。注意到 A?A? 就可以了，因为夹在中间的 ? 的贡献是 $2$ 或 $0$；在后面的 ? 的贡献是 $1$ 或 $0$，可以直接分类算出两个 ? 都是什么。于是这样就是 $\mathcal{O}(2\sqrt{n})$，大概是 $\text{80pts}$。
A?A? 可以根据回答的值的奇偶性来判断最后一个 ? 是啥，那自然 A?A?A?A?A? 也可以。因此，我们每次问 $S$ 个位置，能在此同时得到一个位置的具体值。只需要维护当前已经确定的 $A$ 集合与 $B$ 集合，每次操作之后其中一个会增大 $1$，每次拿 $A,B$ 中较多的一种去问答案。直接通过这个做法，不 “在 $1$ 次操作内问出 $2$ 个位置的确切值” 就可以得到 $\text{80pts}$。
把两种拼在一起，一开始先跑一下 “在 $1$ 次操作内问出 $2$ 个位置的确切值”，后面再做这个扩大集合，可以得到 $\text{92pts}$。
考虑继续优化。后面的部分看起来不太好优化，不妨继续思考要如何把 “在 $1$ 次操作内问出 $2$ 个位置的确切值” 变得更优。题解告诉我们，存在方法能够 “在 $2$ 次操作内问出 $5$ 个位置的确切值”，具体来说这种方法需要 $3$ 个确定的 $A$，和 $B$ 个确定的 $0$（反过来当然也行）。
这个看起来很优，但是必须要 $AB$ 都有的时候才能用。我们希望能尽快达到这种状态。题解告诉我们，还有一种方法，能 “对于五个位置，在一次询问后判断他们是否全 $A$，并在总共 $3$ 步以内，将他们的确切值给求出来”，这种方法只需要 $1$ 个确定的 $A$，这是一开始我们就得到了的。
于是，我们先做第二种，等到第一种能用的时候，转去用第一种。不难发现第二种操作只有在最后一次的时候才会用到 $3$ 次询问，前面都只要一次询问（因为每次确定 $5$ 个位置，只要不是全部相等的就一定可以用第一种了）。于是最差情况下，我们需要 $2k+1$ 次操作确定 $5k$ 个位置。
后面就拼上之前的做法就行了，可以通过。
关于两种操作的具体策略，感觉很难用人脑来构造。主要是因为 $2^5$ 种取值，在第一次询问之后将被划分成若干返回值相等的集合，第二次、第三次询问要在之前划分的集合之间做（即第二步策略可能因为第一步的答案不同而改变）。
不过写个搜就好了，next_permutation 套两层、三层竟然都很快（需要一些方法来避免相同集合的重复计算）。
$\text{stations}$
一个简单的方法是记录树的括号序，然后看 $t$ 的括号序在哪个子树内，这样由于一个点上要压两个数，所以所需数字大小是 $\mathcal{O}(n^2)$ 级别的。
考虑怎么优化上面这个做法。为什么 $\text{DFS}$ 序就不行呢？关键问题在于 $\text{DFS}$ 序只记录了第一次进入这个点的时间，而没有记录从这个点出去的时间，所以在这个子树内的时间区间的右端点是缺失的，使我们不知道应该去最后一个儿子，还是往父亲走。
于是，我们需要一个其他的方法来“框住”右端点。注意到，如果当前在 $x$ 点，则其邻域内一定有他的父亲和他第一个遍历的儿子，所以 $x$ 点的 $\text{DFS}$ 序是完全没有意义的，他就是领域中最小的 $\text{DFS}$ 序 $+1$。不妨用它来“框住”右端点。具体来说，在离开 $x$ 这棵子树的时候，再记录 $x$ 的编号。
这样，$x$ 的标号就代表了“什么时候离开了 $x$ 的子树”，这样就有了完整的时间区间。这告诉我们，只要任意点与其领域内所有点的记录时间不同（进入时记录 / 出去时记录），就能够得到完整的区间。
直接对于深度为奇数的点，在进入时记录；深度为偶数的点，在出去时记录即可。
orzcxy!