P8415 pmrmscxip 题解

Zzzcr · 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。