【题目大意】
给出$n$个数$a_1, a_2, ..., a_n$，求有多少个区间$[l, r]$，满足每个数都出现了奇数次。
$1 \leq n \leq 2 * 10^5, 0 \leq a_i \leq 10^6$
【题解】
稳爷爷出的noi模拟题（原题来自某地区ioi选拔赛）
给每个数赋一个随机权值$H_x$，那么问题转化为：
有多少个区间，使得区间内的数的异或和=区间内出现过的数的异或和。
这是可以分块的，记$lst_i$表示数$i$上一次出现的位置，令$x = H_{a_i}$那么每次就是给$[1, lst_x]$异或一个数，并且询问$[1, i]$中为0的数的个数。
分块+map可以做到$O(n\sqrt{nlogn})$。但是会被卡。
分块+hash就能做到$O(n\sqrt{n})$了，把hash表的取模开到1000~3000较优。每次暴力就重构一次。重构的时空复杂度是正确的。
# include <map>
# include <vector>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h> using namespace std; typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5 + , M = 1e6 + , NB = + ;
const int mod = 1e9+, BLOCK = ;
const int MOD = ; int n, m, B, a[N], bl[N], L[N], R[N];
vector<int> ps;
ull H[N];
int lst[N]; struct hasher {
int head[MOD + ], w[MOD + ], nxt[MOD + ], tot, id, hid[MOD + ]; ull to[MOD + ];
inline void set() {
tot = ; id = ;
memset(head, , sizeof head);
memset(hid, , sizeof hid);
}
inline void reset() {
tot = ; ++id;
}
inline void add(int u, ull v, int _w) {
++tot; nxt[tot] = head[u];
head[u] = tot; to[tot] = v; w[tot] = _w;
}
inline void init(int L, int R) {
add(, , R-L+);
} inline int bg(int x) {
if(hid[x] == id) return head[x];
else {
hid[x] = id;
return head[x] = ;
}
} inline void ins(ull x) {
int hx = x % MOD;
for (int i=bg(hx); i; i=nxt[i])
if(to[i] == x) {
++w[i];
return ;
}
add(hx, x, );
} inline int query(ull x) {
int hx = x % MOD;
for (int i=bg(hx); i; i=nxt[i])
if(to[i] == x) return w[i];
return ;
}
}solver[NB]; inline ull irand() {
ull ret = ;
for (int i=; i<=; ++i) ret = (ret << ) + rand();
return ret;
} ull tag[NB], c[N];
inline void dealxor(int x, ull v) {
if(!x) return ;
int p = bl[x];
for (int i=; i<p; ++i) tag[i] ^= v;
solver[p].reset();
for (int i=L[p]; i<=x; ++i) {
c[i] ^= v;
solver[p].ins(c[i]);
}
for (int i=x+; i<=R[p]; ++i) solver[p].ins(c[i]);
} inline int query(int x) {
int p = bl[x], ret = ;
for (int i=; i<p; ++i) ret += solver[i].query(tag[i]);
for (int i=L[p]; i<=x; ++i) if(c[i] == tag[p]) ++ret;
return ret;
} int main() {
// freopen("odd2.in", "r", stdin);
cin >> n;
for (int i=; i<=n; ++i) {
scanf("%d", a+i);
ps.push_back(a[i]);
}
sort(ps.begin(), ps.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
m = ps.size();
for (int i=; i<=n; ++i) a[i] = lower_bound(ps.begin(), ps.end(), a[i]) - ps.begin() + ;
for (int i=; i<=m; ++i) H[i] = irand();
for (int i=; i<=n; ++i) bl[i] = (i-)/BLOCK + ;
B = bl[n];
for (int i=; i<=B; ++i) L[i] = (i-) * BLOCK + , R[i] = i * BLOCK;
R[B] = min(R[B], n);
for (int i=; i<=B; ++i) solver[i].set(), solver[i].init(L[i], R[i]);
ll ans = ;
for (int i=; i<=n; ++i) {
int pre = lst[a[i]]; lst[a[i]] = i;
// cerr << i << ' ' << pre << endl;
dealxor(pre, H[a[i]]);
ans += query(i);
}
cout << ans;
return ;
}
/*
4
2 2 2 3
Ans = 7
*/