题解：P7722 [Ynoi2007] tmpq

· · 题解

前言

这篇题解是 zak 的做法，我实现得很丑所以常数巨大，但我尽量把我的实现讲清楚（）。

做法

转化 & 暴力

首先，令 b'_i=b_{a_i},c'_i=c_{a_i}，就可以将原题条件转换为 b'_i=a_i=c'_i，那么对 a_i 进行单点修改，其实就相当于对 b'_i 和 c'_i 都进行单点修改。

对于每一种 b'_i=a_i=c'_i=w 的 w，他们的答案数是互相独立互不干扰的，所以可以对每种 w 单独考虑对答案的贡献。

设 dp_{i,1/2/3} 表示考虑前 i 个数中，b'_p=w/b'_p=a_q=w/b'_p=a_q=c'_r=w 的方案数（p<q<r\le i），其中 dp_{i,0}=1，则有

dp_{i,1}=dp_{i-1,1}+dp_{i-1,0}\times [b'_i=w] dp_{i,2}=dp_{i-1,2}+dp_{i-1,1}\times [a_i=w] dp_{i,3}=dp_{i-1,3}+dp_{i-1,2}\times [c'_i=w]

共有 n 种 w，每次修改可能导致 6 种 w 的答案改变，暴力做一次 DP 是 O(n) 的，所以总复杂度是 O(n^2+6nm)

由于 dp_i 只依赖于 dp_{i-1}，所以可以空间压缩成 dp_{1/2/3}，注意转移顺序。

根号分治：小于等于根号的部分

对 w 进行根号分治，统计出 w 在 a_i,b'_i,c'_i 以及修改后，w 的总出现次数 cnt_w（显然 \sum cnt_w=3nm）。按照 cnt_w 的大小根号分治。

对于出现次数 <B 的 w，能够有效更改 dp 的位置不超过 B 个，因此每次涉及到修改 w 的操作时，暴力重做这一次 DP。

使用动态数组 vec_w 存下这 B 个位置，当进行修改操作时，相当于往 vec_w 里添加或删除位置，暴力找到这个位置进行操作，时间复杂度 O(B)。

接着考虑维护前缀和，令 f_i 表示 c'_i=w 且符合题意的方案数，则 f_i=dp_{i,2}\times[c'_i=w]，要维护的就是 f_i 的前缀和。

对序列进行分块，考虑到只需要进行 m 次查询，而暴力重新做 DP 本身已经占据了 O(B) 的时间，所以需要 O(1) 修改，O(\sqrt n) 查询（这里的根号只是象征义）。令 s_i 表示块 i 的 f 的和就可以做到。

根号分治：大于根号的部分

这个 DP 只有四个状态，所以考虑序列动态 DP。

\begin{bmatrix} dp_0 & dp_1 & dp_2 & dp_3 \end{bmatrix} \times \begin{bmatrix} 1 & b'_i=w & 0 & 0 \\ 0 & 1 & a_i=w & 0 \\ 0 & 0 & 1 & c'_i=w \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} dp'_0 & dp'_1 & dp'_2 & dp'_3 \end{bmatrix}

由于出现次数 >B 的 w 小于 \frac{n+m}{B} 个，所以单独考虑每一个 w，O(n) 维护矩阵前缀乘。

由于枚举每种 w 已经消耗了 \sqrt n 的时间，查询数有 m 个，但是总修改数一定也是 m 的级别的（和上面 O(6mn) 一样的道理），所以需要做到 O(1) 查询，O(\sqrt n) 修改。设 SB_i 表示前 i 个块的前缀乘，S_i 表示块的左端点到 i 的前缀乘，那么查询 r 就是 SB_{bel_r-1}\times S_r，修改按照定义修改即可。

取矩阵中的哪个数呢？初始的 \begin{bmatrix}dp_0 & dp_1 & dp_2 & dp_3\end{bmatrix} 是 \begin{bmatrix}1&0&0&0\end{bmatrix}，最终希望得到 dp_3，带进去算可以得到是要矩阵 (0,3) 这个位置的数。

总时间复杂度 O((n+m)B+4^3\times \frac{n+m}{B}\times(n+m))，空间复杂度线性，B 可以取 \sqrt{n+m}，但我取的 B=1000 才能通过（）。

我错的一些细节

可能会出现 cnt_{c'_i}\le B，但是修改后的 cnt_{c'_i}>B，这样他就不会重做 c'_i 的 DP，导致 f_i 不能被消除贡献。

代码细节有点多，都打注释了。