Educational Codeforces Round 95 (Rated for Div. 2) G. Three Occurrences

首先我们随机两个数组\(valA_x,valB_x\)。

对于数组\(a\),记\(cnt\)表示\(a_i\) 在前缀中出现的次数。

1. 若\(cnt\equiv 0 \mod 3\)，则\(b_i=valA_x\)
2. 若\(cnt\equiv 1 \mod 3\)，则\(b_i=valB_x\)
3. 若\(cnt\equiv 2 \mod 3\)，则\(b_i=valA_x \oplus valB_x\)

记\(pre_i\)表示\(b\)的前缀异或和，如果区间\([l.r]\)内每个数的出现次数都是\(3\)的倍数，则满足\(pre_r \oplus pre_{l-1} = 0\)

再用双指针求出\([l,r]\)表示对\(r\)来说的最大区间满足区间内任何一个数出现的次数都不超过3次。此时只要求出满足\(l\le pos\le r \and pre_r \oplus pre_{pos-1}\)的\(pos\)的个数，即可求出\(r\)对答案产生的贡献。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;


#define int i64

using vi = vector<int>;
using pii = pair<int,int>;

i32 main(){
	ios::sync_with_stdio(false), cin.tie(nullptr);
	mt19937_64 rd(time(0));

	int n;
	cin >> n;
	vi valA(n + 1), valB(n + 1);
	for(int i = 1; i <= n; i ++)
		valA[i] = rd(), valB[i] = rd();

	vi cnt(n + 1), a(n + 1), b(n + 1), pre(n + 1);
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		cnt[a[i]] ++;
		if(cnt[a[i]] % 3 == 0) b[i] = valA[a[i]];
		if(cnt[a[i]] % 3 == 1) b[i] = valB[a[i]];
		if(cnt[a[i]] % 3 == 2) b[i] = valA[a[i]] ^ valB[a[i]];
		pre[i] = pre[i - 1] ^ b[i];
	}

	cnt = vi(n + 1);
	map<i64,i32> sum;
	sum[0] = 1;
	int res = 0;
	for(int l = 0 , r = 1; r <= n; r ++) {
		cnt[a[r]] ++;
		while(cnt[a[r]] > 3) {
			cnt[a[l]] --;
			if(l > 0) sum[pre[l - 1]] --;
			l ++;
		}
		res += sum[pre[r]], sum[pre[r]] ++;
	}
	cout << res << "\n";
	return 0;
}