CF1418G Three Occurrences 做题笔记

题目链接

题意是输出所有区间满足其内部每个数要么出现 $3$ 次要么不出现的个数。

因为是区间，数量很多，发现贡献是可以抵消的，直接无脑预处理前缀的桶。

然后枚举左端点，统计答案，怎么处理呢？

疯狂地向右扩展，直到区间内有数字出现了 $3$ 次以上（这样是对的，待会儿证明，另外扩展到前一个就够了，不要到有数字出现了 $4$ 次）。

现在的区间内出现的数字都是 $3$ 次及以下了，接着看这个区间内有没有合适的前缀桶 $b$，$b$ 的每一项减去 $1\cdots l-1$ 这个前缀的桶 $c$，然后得到一个新的桶 $d$，如果 $d$ 内元素都是 $0$ 或 $3$，那么合法的答案就多了一个。

现在我们发现桶内的元素值已经不重要了，重要的是对 $3$ 取模的结果对吧？这样如果两个前缀桶 $b$ 和 $c$ 相减能构成答案，那么这两个桶的每一项元素就必定相同了吧。

如何维护两个桶是否相同呢？暴力还是行不通的，我们可以把它从高到低看成一个 $13331$ 进制的数（

这么大的数还是存不下啊，我们把它对一个质数取模就行了，然后再开一个桶维护前缀桶就能快速找到在给定的区间内与桶 $d$ 大概率相同的桶啦。

再来看下那个的证明，假设有个合法的区间 $l$ $r$，那么它中的所有元素出现个数一定小于等于 $3$，所以在以 $l$ 为左端点扩展时一定会扩展到 $r$ 了，所以一定会被统计到。

这样会不会重复统计呢？当然不会，我们把答案分左端点统计了啊。

然后单模数哈希过不了，写了双哈希。

#include <unordered_map>
#include <time.h>
#include <iostream>
#define int long long
using namespace std;
const int mod1 = 998244353, mod2 = 1000000009;
int n, l, r, ans;
int a[500005], s[500005], s1[500005], s2[500005];
int p1[500005], p2[500005];
unordered_map <int, int> b, w, b_;
signed main () {
    cin >> n;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i ++) {
        p1[i] = p1[i - 1] * 13331 % mod1;
        p2[i] = p2[i - 1] * 13331 % mod2;
    }
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) {
        ++ b[a[i] ];
        s1[i] = s1[i - 1] + p1[a[i] ];
        s2[i] = s2[i - 1] + p2[a[i] ];
        if (s1[i] >= mod1) s1[i] -= mod1;
        if (s2[i] >= mod2) s2[i] -= mod2;
        if (b[a[i] ] == 3) {
            b[a[i] ] = 0;
            s1[i] -= p1[a[i] ] * 3;
            s2[i] -= p2[a[i] ] * 3;
            s1[i] = ( (s1[i] % mod1) + mod1) % mod1;
            s2[i] = ( (s2[i] % mod2) + mod2) % mod2;
        }
        s[i] = s2[i] * 1000000011 + s1[i];
    }
    b.clear ();
    for (l = 1; l <= n; l ++) {
        while (1) {
            if (r != n && b_[a[r + 1] ] != 3) {
                ++ b_[a[++ r] ];
                ++ b[s[r] ];
            } else break;
        }
        ans += b[s[l - 1] ];
        -- b_[a[l] ];
        -- b[s[l] ];
    }
    cout << ans;
    return 0;
}