自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 22:56:45，当前版本为作者最后更新于2024-06-05 23:40:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这种码量的数据结构题感觉放到正式考场上做出的概率 < 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 分开看还是相当容易的）