CF1588 [F] Jumping Through the Array

· · 个人记录

第一反应肯定都是先画个图看看它三个操作都在干什么：

【这里应该有个图，但是懒得放了】

但是没什么用，并没有什么好的性质，因为这个 3 操作非常恶心，可能会合并环或者断开环。

考虑只有 1,2 操作怎么解决。感觉它给了 8s 就算 \rm polylog 也大概率是两只，而根号就可以打爆它，所以考虑根号平衡。

操作 2 是打 tag，操作 2 直接找到 所有有 tag 的 环算出与询问区间的交就可以计算了，由于上面加粗的这个限制和修改次数相关，考虑每 \sqrt{n} 个修改下放所有标记，那么每次满足条件的环只有 O(\sqrt{n}) 个，复杂度 O(n \sqrt{n})。

注意到这个根号重构的思想很深奥，我们尝试把它推广到有操作 3 的情况。

考虑一块 \sqrt{n} 个操作，则所有环上被改变的点有 O(\sqrt{n}) 个，而环上在这些点两两之间的所有点之间的形态不变（也就是从一个关键点的后继走到下一个关键点的前驱，这样的一段形态在这块操作里面是静态的），于是可以把每一段直接缩成一个点。那么这块操作过程中全局的点数变成了 O(\sqrt{n})。那么操作 2 可以暴力枚举所有点判断能否到达做到 O(\sqrt{n})，操作 1 只需要对每个点求出它内部包含多少个在区间里的原来环上的点，这个可以直接二分，调整好块长可以做到 O(\sqrt{n \log n})；但是可以做到更优秀，但是我不会你们自己去看题解吧！！！1