2021联合省选题解

由于 DPair 很懒，这里只有他 A 了的题

D1T1 打牌

首先不难发现，我们翻面的必然是一段前缀和一段后缀。

其实也很好证明。我们假设有三张卡牌 $(a_i, b_i)$, $(a_j, b_j)$ $(a_k, b_k)$ ，其中 $i < j < k$ 。

那么假设 $i, k$ 均不被翻面，则答案必然不小于 $a_k-a_i$ ，也就是说，翻 $j$ 必然起不到减小答案的作用。

所以必然是选一段前缀和一段后缀。

然后我们考虑枚举前缀快速求出最优后缀。

我们设 $b$ 的后缀最大值和最小值分别为 $c, d$ ，然后设当前前缀的最大值与最小值为 $mn, mx$ 。

那么每一次我们要求的就是

$$\min_i \{\max(mx, a[i-1], c[i]) - \min(mn, a[cur], d[i])\}$$

这里 $i$ 表示后缀的位置且默认满足 $m$ 的限制， $cur$ 表示当前枚举到的前缀的位置。

显然这里面有很多常量，我们把这些常量与 $mn, mx$ 合并。

那么最终要求的就是这么个式子

$$\min_i \{\max(mx, a[i-1], c[i]) - \min(mn, d[i])\}$$

然后我们再合并与 $i$ 有关的项，得到

$$\min_i \{\max(mx, c[i]) - \min(mn, d[i])\}$$

不难 $d$ 有单调性，现在的 $c$ 先减后增。

那么我们考虑找出 $c$ 先减后增的分界点，那么前后两部分都可以二分处理。

这样是 $O(n\log n)$ ，已经可以通过本题。

D2T1 宝玉兽

首先，这个 $p$ 数组直接给他离散化掉，显然没有问题，那么现在每一个数的下一个就是它自己 $+1$ 。

然后这东西可以树分块，但是我懒得写。

然后这东西可以主席树但是我懒得写。

然后这东西甚至可以点分治但是我不想写。

然后这东西可以倍增，诶这个好写写这个。

具体来说就是扫一遍整棵树然后实时记录每一个权值当前的最低位置，然后每一个点维护出它往上的第一个 $1$ 和第一个 $a[i]+1$ ，类似一个子序列自动机。

然后就可以倍增了。

但是不难发现这样只能处理上行路径。

因此我们考虑怎么处理下行路径。

注意到这道题可以离线，因此我们把每一个询问转化成 $(x, id)$ 的二元组，表示这个询问当前数为 $x$ ，为第 $id$ 组询问，然后在结束点打一个对应编号的标记。

然后我们用类似第二分块的并查集，同一个并查集表示答案为 $x$ 的所有点，这个显然很好维护。

但是需要可撤销并查集，多一只 $\log$ 。

因此最终复杂度 $O(n\log n)$ ，我们为了方便认为所有东西都同阶。

赛后和 Jacderzhang 胡了一下发现这个做法很有前途，把可撤销并查集改成 $\text{log Tree}$ 似乎可以把复杂度变成 $O(n\log n \log \log n + q\log\log n)$ ？