题解：P10305 [THUWC 2020] 序排泡冒

· · 题解

这种码量的数据结构题感觉放到正式考场上做出的概率 < 10%......在相对冷静的情况下也从 20：40 开始看题，不看题解做到 23：20 才完成调试和卡常，成功通过。（而且还是 IOI 赛制的情况下，虽然没测大样例）

首先考虑给定一个序列 [p_1,p_2,\dots p_n] 怎么快速求解。由经典结论，设 c_i 为 p_1,p_2\dots p_{i-1} 中比 p_i 大的数量，那么每经过一轮冒泡排序，c 序列的每一项 c_i 都变化为 \max(0,c_{i}-1)，接着整个 c 序列整体左移一位，删除 c_1，末尾补 0。

那么现在我们得到了 k 轮冒泡排序后的序列，相当于已知 k 轮后的 c 序列，那么倒退回 k 轮前，对于 c'_{k+1},\dots ,c'_n，如果 c_{i}>0，那么 c'_{k+i} 必然为 c_i+k，否则，c'_{k+i} 可以取 [0,k] 中任意值。综上，容易总结得到答案为 k!(k+1)^{q-k}，其中 q 为前缀最大值的数量。（当然还需要特判无解的情况，即 p 的最后 k 个元素非单调或最后 k 个不是最大的 k 个的情况）

现在问题转化为给定树上一条链，求出前缀最大值数量。有很容易的 \mathcal O(n\log^3n)：考虑树剖 + 楼房重建线段树，在 dfs 序列上建立线段树，维护每个节点最大值和前缀最大值的数量。（不展开细节，见 P4198）（考场上想不清楚的时候，性价比最高的做法，因为在链上是 \mathcal O(n\log^2n) 可以直接顺带通过，而且树剖和楼房重建线段树常数都不大，应该可以通过除了最后一个包以外的所有点，个人预计半小时就能写完调完）

但是现在是赛后，我们不能止步于此。考虑更细致地分析性质。设路径为 x\to lca\to y，那么 x\to lca 这一段是容易分析的，每次向上跳到最近的比当前点权值大的最深的点即可，这个点是可以预处理出来的，预处理后建立倍增数组即可。假设现在在 lca 之前跳到的最后一个点是 u。

我们现在要求 u\to lca \to y 的前缀最大值数量。 u\to lca 这段上已经没有新的最大值了，所以我们要找到 lca\to v 路径上第一个 >p_u 的点。这个点可以通过树链剖分，拆分成 \mathcal O(\log n) 条链，依次枚举每条链，如果这条链上已经有 >p_u 的点了（区间最大值，st 表 \mathcal O(1) 查询），就在这条链内部二分。每次查询只会二分一次，复杂度是 \mathcal O(\log n) 的。设这个点为 v。

最后剩下 v\to y 这一段。我们已经预处理了每个点往上第一个比他大的点，设其为 t_u，那么一个这段路径上的点 w 被计算贡献当且仅当 dep_{t_u}<dep_{lca}（如果 \ge dep_{lca} 显然就被半路掐掉了），这是一个链上一维数点，可以离线之后 dfs 一遍树，用树状数组维护。

别忘了前面一个预处理没有解决。回顾一下，我们需要求出每个点上面第一个比他大的点，一个 naive 的想法是 dfs 的同时维护单调栈，每次直接二分一个点，但是直接维护显然 push，pop 次数可能达到 \mathcal O(n^2)，需要可持久化的结构，但是这就很麻烦了。还不如直接建立一棵线段树，每次二分一个后缀即可。时间复杂度 \mathcal O(n\log n)。

还剩下一个判断是否有解。最后 k 个数是递增的是好判断的，直接前缀和就行了。判断是否是最大的 k 个只需要求出前缀的 \max 和后缀的 \min 进行比较即可。复杂度也是 \mathcal O(n\log n) 的。

综上，总时间复杂度为 \mathcal O(n\log n)。常数比较大，建议不要到最后来卡常，写的过程中就注意实现。

代码实际上预处理部分写了 \mathcal O(n\log^2n)，因为这个常数小，对效率影响不大。（共 6kb，但是想清楚了每个 part 分开看还是相当容易的）