自动搬运

查看原文

来自洛谷，原作者为

	Nopain **

搬运于2025-08-24 23:06:45，当前版本为作者最后更新于2025-04-09 23:11:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一些字打了又删，犹豫再三也没把老年选手的碎碎念放出来，无病呻吟应该是没人愿意看的。

以下视 $n,m$ 同阶，于是不再区分二者。

考虑分治，处理跨过分治中心 $\text{mid}$ 的询问。

思考一下这个来回跳的过程，大概就是先在一边跳一会，然后跨过 $\text{mid}$，再跳一会再跳回来，可以将跳跨过 $\text{mid}$ 视为先跳到 $\text{mid}$ 再接着跳，于是两边分为独立的过程，于是思考两边各自贡献了多少距离，不妨只考虑右边。

显然只有右边排序后 $a_i,a_j$ 相邻的点对才有贡献。贡献形式有如下两种：

• 若左侧不存在 $k$ 满足 $a_i<a_k<a_j$，则我们会直接从 $a_i$ 跳到 $a_j$，答案贡献距离为 $c_0=|i-j|$。

• 否则会从 $a_i$ 跨过 $\text{mid}$ 跳到左边，不知道跳多少次再跳回到 $a_j$，只算右边的贡献是 $c_1=i-mid+j-mid$。

所以我们需要计算所有点对 $(a_i,a_j)$ 在左侧是否存在中间的数，可以想到我们只需要保留所有在其之间的数中最靠右的，设其位置为 $p_i$。则在询问时对右侧包含的每个点对考虑，若 $ql\le p_i$，则 $(a_i,a_j)$ 贡献为 $c_1$，否则为 $c_0$。

以上都是暴力，考虑如何用数据结构维护这个过程。考虑到点对 $(a_i,a_j)$ 维护着一个分界点 $p_i$，而点对的合并是容易的，将两个 $p$ 取 $\text{max}$ 即可。而分裂是困难的，需要额外的数据结构维护。于是我们从 $\text{R}$ 向 $\text{mid}$ 倒着扫描线，维护删除点对的过程。删除一个点 $a_i$ 时删除其前驱点对 $(a_p,a_i)$ 和后继点对 $(a_i,a_s)$ 的贡献，再加入点对 $(a_p,a_s)$，前驱和后继可以用链表维护，这里共进行了 $O(n\log n)$ 次修改。而查询时则变为了动态一维数点，使用树状数组即可做到 $O(n\log^2 n)$。

我们发现修改和查询存在不平衡，考虑使用 $O(n^{\epsilon})$ 分块来平衡这一点。如果以前见过这个套路即可平衡得时间复杂度为 $O(\frac{n\log^2 n}{\log\log n})$。不会也没关系，我下面讲。

考虑线段树即可视为 $2$ 叉树，分块可视为 $\sqrt n$ 叉树。那么一般的，用一个 $h$ 叉树维护长为 $n$ 的序列，树高为 $\log_h n$。此时单点修改复杂度为 $O(\log_h n)$，查询复杂度为 $O(h\log_h n)$，当然两边复杂度也可以反过来。

回到上面的问题，我们有 $O(n\log n)$ 次修改与 $O(n)$ 次查询。若使用 $h$ 叉树使得复杂度最优则需要两侧复杂度相同，即 $n\log n \log_hn=nh\log_hn$，解得 $h=\log n$，运用换底公式带入得复杂度为 $O(\frac{n\log^2 n}{\log\log n})$。

看起来大部分人都能轻松通过，但我被卡了好久的常，所以在这里说一下我的卡常方法：

0. 加快读，少开 $\text{long long}$，没询问就不要跑这一大坨。

1. 扫描线建议按询问排序扫，扫完所有询问了即使后面还有点对需要删就可以不用额外加点对了，访问链表顺次删除贡献即可。

2. $h$ 叉树不要显式建出来，不然需要类似线段树的递归式写法会很慢，算算块长用迭代分块代替，我最底层分块块长为 $25$。

3. 递归到底层可以跑暴力，我设的阈值为 $\text{len}\le 65$，瞎试出来的，其实可以跑一下看看分治长度都有哪些。

4. 随着分治区间长度不同，一维数点的值域大小不总是 $n$。随着分治区间减小可以缩小维护范围，能小一些常数。

5. 当分治子树内总询问数不超过某阈值，可以直接将内部排序跑暴力。我试过没有显著效果，但如果卡不进去可以试试。

6. 能加 $\text{inline}$ 就加，有效果。

7. 洗把脸多交几次就过了，亲测有用。

需要代码的可以私信我，但我写的一坨屎，还是别来找我污染你数据库了吧。