题解：
看到奇数时就应该想到随机的，最近两次遇到这种题了。
考虑给每一个数随机一个权值(v[i])。
一个区间([x,y])所有数的出现次数是奇数，相当于(v[x..y])的异或和 等于 (la[i]<x且x<=i<=y ~v[i])的异或和。
设(s)表示(v)的前缀异或和。
从左往右枚举(y)，记(p[x])表示(la[i]<x且x<=i<=y ~v[i])的异或和。
相当于求(s[x-1]⊕p[x]⊕s[y]=0)的(x)的数量。
随着(y)右移到(y+1),会使(p[la[y+1]+1..y]⊕=v[y+1])
那么问题就变成了：
1.对p的一个区间异或上一个数
2.查询(p)中(=s[y])的个数。
考虑用分块维护，每一块存一个hash表和lazytag以支持查询。
时间复杂度：(O(nsqrt n))
hash表分开建会快，从别人的代码里学到一个写hash表的新姿势：
struct hash_table {
//...
int& operator [] (long long n) {
//...
}
} h[N];
//在外面可以直接调用h[...][...]
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
#define ul unsigned long long
ul rx = 1e9 + 7;
ll rand(ll x, ll y) {
rx *= 998244353;
return rx % (y - x + 1) + x;
}
const int M = 1e6 + 5;
ll rv[M];
const int N = 2e5 + 5;
int n;
ll a[N], s[N];
int la[N], ed[M];
void Init() {
fo(i, 0, 1e6) rv[i] = rand(1, 1ll << 60);
scanf("%d", &n);
fo(i, 1, n) {
scanf("%lld", &a[i]);
la[i] = ed[a[i]];
ed[a[i]] = i;
a[i] = rv[a[i]];
s[i] = s[i - 1] ^ a[i];
}
}
namespace fk {
const int blo = 400;
const int C = N / blo + 5;
const int M = 20007;
struct nod {
int fi[M], d[blo + 5], d0;
int nt[blo + 5], cnt[blo + 5], td;
ll h[blo + 5];
void _new() {
fo(i, 1, td) cnt[i] = 0;
fo(i, 1, d0) fi[d[i]] = 0;
td = d0 = 0;
}
int& operator [] (ll n) {
int y = n % M;
for(int p = fi[y]; p; p = nt[p])
if(h[p] == n) return cnt[p];
if(fi[y] == 0) d[++ d0] = y;
nt[++ td] = fi[y], fi[y] = td, h[td] = n;
return cnt[td];
}
int find(ll n) {
int y = n % M;
for(int p = fi[y]; p; p = nt[p])
if(h[p] == n) return cnt[p];
return 0;
}
} c[C];
int id[N], id0, l[C], r[C];
ll v[N], lz[C];
void cg(int w) {
c[w]._new();
fo(i, l[w], r[w]) c[w][v[i]] ++;
}
void build() {
fo(i, 1, n) {
if(i % blo == 1) l[++ id0] = i;
id[i] = id0; r[id0] = i;
}
fo(i, 1, n) v[i] = s[i - 1];
fo(i, 1, id0) cg(i);
}
void cha_b(int x, int y, ll z) {
fo(i, x, y) v[i] ^= z;
cg(id[x]);
}
void cha(int x, int y, ll z) {
if(id[x] == id[y]) return cha_b(x, y, z);
cha_b(x, r[id[x]], z); cha_b(l[id[y]], y, z);
fo(i, id[x] + 1, id[y] - 1) lz[i] ^= z;
}
int qry_b(int x, int y, ll z) {
z ^= lz[id[x]]; int s = 0;
fo(i, x, y) s += (z == v[i]);
return s;
}
int qry(int x, int y, ll z) {
if(id[x] == id[y]) return qry_b(x, y, z);
int s = qry_b(x, r[id[x]], z) + qry_b(l[id[y]], y, z);
fo(i, id[x] + 1, id[y] - 1) s += c[i].find(z ^ lz[i]);
return s;
}
}
void work() {
ll ans = 0;
fo(i, 1, n) {
fk :: cha(la[i] + 1, i, a[i]);
ans += fk :: qry(1, i, s[i]);
}
pp("%lld
", ans);
}
int main() {
Init();
fk :: build();
work();
}