题解：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$，则有

共有 $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。

由于出现次数 $>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$ 不能被消除贡献。