自动搬运

查看原文

来自洛谷，原作者为

	Zzzcr **

搬运于2025-08-24 22:38:51，当前版本为作者最后更新于2024-11-11 21:59:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

模拟赛搬了，没写出来，深刻体会到自己代码能力的弱小。

我们称一段连续满足限制的区间为一个连续段，a 序列上的一个连续段的颜色集合显然由 b 序列给出的置换环上重标号后的至多两个区间构成。

把查询时被砍成两半的边界连续段暴力算下贡献。于是剩下的连续段就都是整段了。对于每个置换环分别维护。把一个区间的贡献刻画到平面上，大概就是原序列下标 $[l,r]$，在置换环上的下标 $[a,b]$，就放一个 $x\in[l,r],y\in[a,b]$，权值为 $r-l+1$ 的矩形。

一次查询 (不妨假设没有被截断的连续段) $(L,R,k)$ 相当于是求 $L\le l,r\le R,y=k$ 的最大权值，注意到任意时刻的区间 $[l,r]$ 是不交的。于是可以不考虑 $r\le R$ 的限制，也就是等价于求 $L\le x\le R,y=k$ 这条线段所截的最大权值。

这个维护是简单的，对每个置换环建出线段树，来支持 $y\in[a,b]$ 区间插入二元组 $(l,r)$，再在线段树的叶子节点上建个平衡树，当 pushdown 到叶子节点时把 $[l,r]$ 插入平衡树即可。查询时只需要在一棵平衡树里取出 $l\in[L,R]$ 这个区间，查下区间 $len_{max}$ 即可。注意这里实现需要做节点回收，否则空间复杂度是假的。

时间 $\mathcal{O}(n\log^2n)$，空间线性。

upd on 2024.12.20:

空间复杂度是 $\mathcal{O}(n\log n)$，之前分析错了/lh。顺便给出一个时空常数更优的做法：

给每个线段树节点开个平衡树，修改的时候直接在区间上修，查询的时候在所有包含它的线段树节点上查询。这样可以过加强版 P10151。