CF1588F Jumping Through the Array

· · 题解

CF1588F Jumping Through the Array

题面

给定 a_n 和排列 p_n ,对每个 i 建有向边 (i,p_i) , q 次操作:

n\le 2\times 10^5,8s

法1

第一眼看成在内向基环树森林上做这个问题///fn,好吧其实是一堆环.

那么第三个操作会把环断开或合并,稍微考虑一下发现断开和合并是十分"自由"的,也就是说找不到多大性质.

于是通过根号分治,序列分块与一堆平衡树可以想到各种根号 $\log$ . 考虑假设没有对环的修改,你直接时间分块,那么可以直接维护所有环,加就直接加到环上,区间和可以直接遍历被加的所有环去算对这个区间的贡献,每根号个重构.那现在有了对环的修改,考虑在根号个修改的情况下,你只切了根号刀,所以实际上可以看成一共只有根号个点集,那么加就直接遍历环包含的每个点集加,询问考虑被加的每个点集的贡献,这里不需要二分,而是直接处理出每个数在这个块里被询问分成的根号段中的哪一段,那么直接对每个环前缀和即可.最后复杂度单根号. ### 法2 我们糊出了不用时间分块的做法! 考虑根号分治,那么在没有3操作的情况下,小块加法直接暴力加到序列上,大块加法把标记打在大块上,那么查询的时候就查询序列上的和,遍历每一个大环,就行了. 现在有了合并/分裂,仍然根号分治,考虑对于一个大环,维护的结构是一个块状链表,链表上每一块维护其在原序列上的每一块的元素个数,及其前缀和.于是考虑: - 查询 - 分成整块和散块 - 整块部分和遍历每一个大环的块状链表上的每一块,就能 $O(1)$ 查询这一块其对序列上整块的和的贡献 - 散块部分若属于某个大环,就直接查每个位置所属的大环的那个块的加法标记. - 加法 - 大环:遍历大环上的每一块,打加法标记,复杂度根号 - 小环:暴力加到序列上 - 合并 - 就是把两个块状链表接起来,可能会合并块状链表上的两块,合并是根号的. - 拆分 - 把一个块状链表拆成两个,可能会把大块中间劈开. 合并拆分都是块状链表经典操作,不再赘述. 注意复杂度分析的时候,块状链表的块的总个数是根号的,因为一个大环的块状链表上小于根号的块左右必然都是大于根号的,而小环我们不开块状链表.所以复杂度单根号.