自动搬运

查看原文

来自洛谷，原作者为

	qiuzx GGMU

搬运于2025-08-24 22:46:53，当前版本为作者最后更新于2024-01-13 11:19:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

给定一个大小为 $n$ 的排列 $p_i$，构造一个无向图，其中 $i<j$ 有边当且仅当 $p_i>p_j$。对于每个 $i$，求它到所有点的最短路之和，若两个点不连通最短路记作 $0$。$n\le 2\times 10^5$。

思路

首先容易发现若某个 $i$ 满足 $\forall j\le i,p_j\le i$，则 $[1,i]$ 与 $[i+1,n]$ 之间不可能相互到达，所以整个图被分成两个连通块。找到所有这样的 $i$ 就能将图分为若干连通块，对每个连通块分别计算答案即可，下面假设整个排列连通，考虑如何计算答案。

由于最短路本身并没有什么比较好的性质，所以对每个 $x$ 求 $i$ 与 $x$ 之间的最短路不太现实。因此考虑将 $\displaystyle\sum_x dis(i,x)$ 转化为 $\displaystyle\sum_t\sum_x[dis(i,x)\ge t]$，即对于每个 $t$ 计算最短路至少为 $t$ 的点的数目求和。那么我们从 $1$ 开始先手动分析一下满足 $dis(i,x)\ge t$ 的点要满足什么性质。这里由于左右两侧是对称的，所以现在只考虑 $x<i$ 的情形，另一侧将排列翻转之后再做一次即可。

当 $t=1$ 时，由于整个排列连通，所以显然答案是 $i-1$。

当 $t=2$ 时，所有满足 $j<i,p_j<p_i$ 的点都不能一次被到达。

当 $t=3$ 时，考虑一个点 $j$ 什么时候能在两步之内到达。假设第一步向左走，则一定是走到最左侧的一个点最优。假设最左侧能到达 $l$，但 $l$ 下一步不能到达 $j$，而存在另一个点 $x$ 能够到达 $j$。由于 $x$ 能一步到达 $j$，而 $i$ 一步无法到达 $j$，所以此时满足 $x<j<i$ 且 $p_x>p_i>p_j$。然而 $l<x,p_l>p_i$，所以 $l$ 也可以一步到达 $j$，矛盾。类似地，可以证明若第一步向右走，则一定是走到 $p_x$ 最小的点最优。这样只需要求出最左能到达的点 $l$ 和最右能到达的点 $r$，那么若 $j$ 既不能被 $l$ 到达，也不能被 $r$ 到达，则 $dis(i,j)\ge 3$。这个条件相当于 $j<l$ 且 $p_j<p_r$。

类似上一种情况继续探索 $t=4,5$ 时的最优策略可以发现，如果不是一步可以到达，从一个点要么走到左侧最靠左的点，要么走到右侧最靠下（即 $p$ 最小）的点。并且若前一次走最左侧的点，那么下一次一定走最下侧的点（否则只能走到它自己）。而这样能够走到的两个点对应了所有不能走到的点的一个右边界和上边界，所以这是一个比较好的形式。具体来说，记 $u_i$ 表示 $i$ 向左能走到的最左侧的点，$d_i$ 表示 $i$ 向右能走到的最下侧的点，那么如果用 $(a_t,b_t)$ 表示 $dis(i,j)\ge t$ 时需要满足 $j<a_t,p_j<b_t$，可以得出结论：$(a_2,b_2)=(i,i)$，$(a_{t+1},b_{t+1})=(u_{b_t},d_{a_t})(t\ge2)$。所以一个暴力的做法就是求出 $u,d$ 之后枚举 $t$，然后一次对答案的贡献形如一个矩形的元素个数，可以预处理，复杂度 $O(n^2)$。

继续优化需要一个比较感性的认知，如果将 $(x,y)$ 向 $(u_y,d_x)$ 连边会形成一棵内向树，像这种遵循某种规律跳来跳去的情况往往意味着会有很多重复的点。因此猜测从所有 $(i,i)$ 开始能够到达的点个数并不多。下面来证明这个点数是 $O(n\sqrt n)$ 级别的。根据点的生成过程容易归纳证明每个有用的点 $(x,y)$ 都满足 $x<y,p_x>p_y$（除了 $(i,i)$，但这些点可以忽略不计）。对于每个 $x$，假设所有 $y>x,p_y<p_x$ 的点为 $b_1<b_2<\cdots<b_k$，我们取出这个序列中的前 $\sqrt n$ 个元素和 $x$ 组成元素对 $(x,b_i)$，则所有这样的元素对个数不超过 $O(n\sqrt n)$。称所有不满足 $i\le \sqrt n$ 的元素对 $(x,b_i)$ 是坏的。下面需要计算有多少个坏的元素对是有用的。这里考虑对于每个 $i$，从 $(i,i)$ 移动到头的过程中会经过多少个坏的元素对，将这些求和得到的结果一定不小于有用的坏元素对数（因为可能算重）。注意到由于对于一个 $x$，$b_1>x$，所以坏元素对 $(x,y)$ 一定满足 $y-x>\sqrt n$。从 $(x,y)$ 下一步会跳到 $(u_y,d_x)$，而显然有 $u_y\le x,d_x\le y$，所以遇到一个坏元素对之后跳一次会使得 $x+y$ 的和减去至少 $\sqrt n$，且 $x+y$ 不可能增加，所以一次跳的过程总共有不超过 $O(\sqrt n)$ 个坏元素对，总数不超过 $O(n\sqrt n)$。显然一个有用的元素对要么是好的要么是坏的，所以总数不超过 $O(n\sqrt n)$。

这样就很容易做了，因为可以对每个有用的元素对计算权值直接在树上求和。假定现在通过某种方式将树建出来了，则需要做 $O(n\sqrt n)$ 次矩形求和，可以使用二维数点做到 $O(n\sqrt n\log n)$。然而注意到树上父亲节点 $(x,y)$ 与儿子节点 $(x',y')$ 一定满足 $x\le x'$，所以从小往大对 $x$ 扫描线做单点加区间求和，这样求出来的贡献是可以直接从父节点加过来的。这样不需要离散化也不需要排序，只需要能够做 $O(n)$ 次单点加，$O(n\sqrt n)$ 次区间求和即可。这个可以平衡复杂度用分块做到 $O(n\sqrt n)$。下面问题只在于建树。这里提供两种方法：

第一种比较直接一些，就是从每个 $(i,i)$ 开始跳，用哈希表记录哪些点对已经有过了，一直跳到一个已经访问过的点结束。这样复杂度是 $O(n\sqrt n)$，常数比较大。

第二种更加巧妙，实现也更简单。注意到 $u,d$ 是有单调性的（值得注意的是一个单调性是位置单调，一个单调性是值单调，实现的时候要注意加以区分），所以倒序扫描 $x$，对于每个 $x$ 动态维护所有有用的点对 $(x,y)$，则在处理到一个 $x$ 的时候加入 $(x,x)$，然后对于每个当前存在的点对 $(x,y)$，将它的下一步 $(x',y')$ 在 $x'$ 对应维护的点对中插入。由于 $u,d$ 的单调性，一个 $x$ 内储存的所有点对的 $y$ 是单调不增的（也可能是单调不降，取决于实现方式），所以在插入的时候判定是否存在只需要判定维护的最后一个点对是否为 $(x',y')$ 即可，如果不是就新开一个点加入。这样复杂度也是 $O(n\sqrt n)$，但不需要写哈希表，常数更好。

代码