题解 CF1418G 【Three Occurrences】

· · 题解

这个题老厉害了。

看到这个题的第一想法是这样的：

考虑枚举右端点，维护合法的左端点个数。这玩意属实可以线段树搞。思维简单，实现也不难。

但有一种很牛逼的只要写十行的做法。

先考虑长度是 3 的倍数怎么做。

我们考虑维护每个前缀的每个数的出现个数 cnt_{i, j}，表示前 i 个数中数 j 出现的次数模 3 的值。

那么一段区间 [l, r] 符合条件当且仅当 cnt_{l-1} = cnt_r。容易哈希。

至于恰好为 3？扫描线一下就没了。

放个代码链接。https://www.luogu.com.cn/paste/3t04xvxn。