偶数次子区间个数

题意

有序列 \(S(n \leq 10^5, S_i \leq 10^6)\), 问区间 \([l, r]\) 内满足每个数出现偶数次的子区间个数。

转化

想到区间出现每个数偶数次，那么异或和一定为 0。

但是异或和为 0 的区间每个数不一定出现偶数个。

于是对相同的值赋一个 \([0, 2^{64}）\) 内随机的值。

这样出现冲突的概率很低。

莫队

剩下问题转化为前缀异或，找相同异或值的数即可。

代码

#include
using namespace std;

using ll = long long;
const int MAXN = 1000010;
const int INF = 0x7fffffff;
const int mod = 1000000007;

template 
void Read(T &x) {
	x = 0; T f = 1; char a = getchar();
	for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
	for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
	x *= f;
}

int n, m, len;
int a[MAXN], cnt[MAXN]; 
ll mp[MAXN], Xor[MAXN], b[MAXN]; 

struct ques {
	int l, r, id;
}q[MAXN];
int ans[MAXN], belong[MAXN]; 

int main() {
	mt19937 rd(1145141919); 
	cin >> n; 
	for (int i = 1; i < MAXN; i ++)
		mp[i] = rd() % (1ll << 63);
	int siz = sqrt(n);
	for (int i = 1; i <= n; i ++) {
		cin >> a[i]; 
		Xor[i] = Xor[i - 1] ^ mp[a[i]];
		b[++ len] = Xor[i];  
		belong[i] = (i - 1) / siz + 1;
	}  
	b[++ len] = 0;
	a[0] = 1;
	sort(b + 1, b + len + 1);
	len = unique(b + 1, b + len + 1) - b - 1;
	for (int i = 1; i <= n; i ++)
		a[i] = lower_bound(b + 1, b + len + 1, Xor[i]) - b; 
	
	 
	cin >> m;
	for (int i = 1; i <= m; i ++) 
		cin >> q[i].l >> q[i].r, q[i].l --, q[i].id = i;
 	sort (q + 1, q + m + 1, [](ques x, ques y) {
 		if (belong[x.l] ^ belong[y.l]) return belong[x.l] < belong[y.l];
 		if (belong[x.l] ^ 1) return x.r < y.r;
		return x.r > y.r;	
	 });
	
	int l = 0, r = -1, sum = 0;
	for (int i = 1; i <= m; i ++) {
		while (l > q[i].l) sum += cnt[a[-- l]] ++;
		while (r < q[i].r) sum += cnt[a[++ r]] ++; 
		while (l < q[i].l) sum -= -- cnt[a[l ++]];
		while (r > q[i].r) sum -= -- cnt[a[r --]]; 
		ans[q[i].id] = sum;   
	}
	
	for (int i = 1; i <= m; i ++)
		cout << ans[i] << endl;
	return 0;
}