自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:32:29，当前版本为作者最后更新于2022-02-19 08:25:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先这个问题太诡异了，我们把问题看作可以对 $a$，$b$，$c$ 都单点修改。要求 $i < j < k$ 的 $b_i = a_j = c_k$ 的对数。

考虑对于 $b_i = a_j = c_k = w$ 的 $w$ 进行根号分治。考虑 $w$ 在 $a,b,c$ 中的总出现次数。

• 对于出现了 $< B$ 次的数，每次对这个数进行修改的时候暴力 DP，在 $k$ 处加即可。

• 对于出现了 $\ge B$ 次的数，这样的数只有 $\Theta(\frac{n+q}{B})$ 个。所以对于每个数维护个动态 DP 即可。

取 $B = \Theta(\sqrt{n+q})$，这两种情况都容易平衡到单次 $\Theta(\sqrt{n+q})$，所以这种做法时间复杂度是 $\Theta(q \sqrt{n+q})$。

目前是 Luogu 最优解。