题解 P8852【[JRKSJ R5] Concvssion】

cyffff · 2022-03-24 13:25:24 · 题解

\text{Link}

题意

给定长度为 n 的序列 a,b，满足 \forall i\in[1,n],a_i,b_i\in[1,n]。

定义一次操作为，\forall i\in[1,n],b_i\gets a_{b_i}。

你需要依次进行 n 次操作，每次操作后求出 \displaystyle\sum_{i=1}^n b_i 对 998244353 取模的答案。

**** 不断被爆标。 ## 思路 ### $a$ 为排列建出 $(i,a_i)$ 组成的图，可知是若干个环。问题变为给出若干个关键点 $b_i$（可重），每次将所有关键点走向连向的点并求所有关键点的编号和。设 $c_i$ 为编号为 $i$ 的结点上有多少个关键点。对于一个环考虑：设其长度为 $l$，则时刻 $i$ 的答案就是时刻 $i\bmod l$ 的答案，只需处理出 $1\sim l$ 时刻的答案。先断环为链，第 $d$ 个时刻的答案 $\displaystyle f_d=\sum_{i=1}^lc_ia_{i+d}$。这个是差卷积形式。具体地，我们令 $a'_i=a_{2l-i+1}$，则 $f_d=\displaystyle\sum_{i=1}^lc_ia'_{2l-d+1-i}$。显然是卷积。我们可以 $O(l\log l)$ 算出 $1\sim l$ 时刻的答案。（这里的 $a$ 是断环为链后链上编号组成的序列）现在用 $O(n\log n)$ 的时间将每个环的答案都求出了，我们考虑计算最终答案。对于 $\text{Subtask }3$，答案直接求了出来，但是对于 $\text{Subtask }4$ ，显然不能对于每一个环枚举时刻。我们考虑将 $l$ 相同的环对应位置的答案相加。考虑到 $l$ 的种类是 $O(\sqrt n)$ 种，此时我们枚举时刻即可。时间复杂度 $O(n\sqrt n)$。 ### $O(n\sqrt n\log n)

本部分是原做法，与最终做法并无太大关联，如需要可跳过。

对于树的部分，考虑转换贡献，考虑一个关键点每个时刻对答案的贡献。

取出关键点到根的路径上的编号，可以对应地加到答案序列中。

考虑对树进行轻重链剖分，建立出 \text{dfs} 序对应形成的序列，让一条重链上的编号在序列中连续。考虑将关键点向上跳重链，每次为将序列中的一个区间一一对应地加到答案序列的一段区间中。

问题形式地说就是给出长为 n 的序列 a,b，m 次操作，每次给出 a 中的一个区间 [l,r] 与 L，执行 \forall i\in[l,r],b_{i+L-l}\gets b_{i+L-l}+a_i。

对于这个问题，我们有如下算法：

对序列 a 按照块长为 B 分块，对于一次操作，若 l,r 同块，则直接加，否则先对散块暴力，整块存下来暂不处理。

所有询问的散块处理完之后，处理整块。对于每个块 [bL,bR]，我们记录 c_i 表示这个块加到 b 序列中以 i 开始的等长区间的次数，d_i=a_{bL+i}(i\le bR-bL)。令这个块对 b_i 的贡献为 res_i，则有 \displaystyle res_i=\sum_{j=1}^i c_jd_{i-j}，可以卷积。

复杂度为 O(mB+\dfrac{(n\log n+m)n}B)，取 B=O(\sqrt\dfrac{n^2\log n+nm}m) 得到最优复杂度 O(n\sqrt{m\log n}+m\sqrt n)，此处 m=O(n\log n)，得到 B=O(\sqrt n)，时间复杂度 O(n\sqrt n\log n)。

建出 (i,a_i) 组成的图，可知是基环树森林。

考虑把上面那两个拼起来，分开的部分分别处理，你会发现还有一个问题：会有点从树上跳到环上。

考虑时间分块（根号重构）：选定 B，每过 B 个时刻重新按照 \text{Subtask }4 的方式预处理一遍所有的环，并将答案加到这次重构到下次重构的 O(B) 个询问中，在这组询问中跳入环中的点（通过深度判断）暴力维护到组末。一次重构的时间复杂度是 O(n\log n+B\sqrt n)，每个点会被暴力维护 O(B) 次，所以环部分的总时间复杂度是 O(\dfrac{n^2\log n}B+nB)，取 B=O(n\sqrt{n\log n})，得到 O(n\sqrt{n\log n})。

树上部分不变，但建树要把环的部分删掉，总时间复杂度 O(n\sqrt n\log n)，空间复杂度 O(n\log n)。

一些卡常技巧：

调块长，树上部分 3000，环上部分 1500；
对于树上部分，如果一个块内没有操作，跳过这个块；
对于环上部分，如果一次重构内没有点跳入环中，与上一个块合并处理。

这三个卡常作用都非常显著，都用上可以把 n\le10^5 的所有点搞进 2s。

这个做法很暴力，并不优美。

O(n\sqrt n)

对树部分进行长链剖分。

对于一个结点，我们考虑将其非长子树内的结点当做长链上同样深度的结点来计算。这样计算显然是不对的，但是我们用非长链上的结点编号减去长链上深度相同的结点编号能得到这个关键点在这个时刻对答案贡献的偏差值。

考虑对于这个结点 x，将其所有非长儿子 q 的所在的长链的结点合并到长儿子 p 所在的长链上。令 f_i 为 q 的 i-1 级长儿子编号减 p 的 i-1 级长儿子编号，g_i 为 q 的 i-1 级长儿子上的关键点数。那么将 q 的所在的长链的结点合并到 p 所在的长链上对时刻 i 答案的偏差就是 \displaystyle\sum_{k=1}^{l}f_{k}g_{k+i}，这是差卷积形式，可以 O(l\log l) 计算。

这么说可能有些难以理解，放张图：

图中，对于结点 3，其有长儿子 6 和非长儿子 4，l=2，f_1=4-6=-2，f_2=5-7=-2。如在 5 处有一个关键点，则 g_2=1，我们会将其看作在 7 处，则对进行了一次操作后的答案的影响为 f_1g_2=-2。

通过以上计算，我们可以将所有树上的关键点合并到所在树的最长链上。考虑将其合并到树所连接的环上，可以将环不断展开至链长，通过以上同样的方法进行偏差的计算。

对于每一个连通块，设其大小为 s，我们做到了 O(s\log s) 的复杂度。

此时总时间复杂度做到了 O(n\sqrt n)，瓶颈在于环的按长度分类算贡献，常数小，在 3\times 10^5 的数据范围下可跑进 1s。

（这里环长分类完加到答案里的时候用指令集加速速度可以起飞。具体实现。）

O(n\log^2 n)

考虑瓶颈是合并若干个连通块的答案，并不优美。

假设我们最终求出第 i 个连通块环大小为 l，第 0\sim l 时刻的答案为 s_{i,p}，考虑写出其生成函数 S_i(x)。

设答案的生成函数是 F(x)，则：

&=\sum_{i=1}^{cnt}\dfrac{S_i(x)}{1-x^{l_i}}\end{aligned}

设 F(x)=\dfrac{P(x)}{Q(x)}，则：

P(x)=\sum_{i=1}^{cnt}S_i(x)\prod_{j\ne i}(1-x^{l_j})

Q(x)=\prod_{i=1}^{cnt}(1-x^{l_i})

分别可以分治 FFT 求出。

实现后发现这个其实跑不过上面那个常数的按环长分类。

再见 qwq~