P7722 tmpq

zhoukangyang · 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 最优解。