题意是输出所有区间满足其内部每个数要么出现 $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; }