题目链接

题意：给你一个数组，求它有多少个子区间所有数都出现了奇数次。$n \leqslant 2 \times 10^5$。

首先给每一个数$\text{rand}$一个权值，那么一个区间满足条件等价于这个区间所有数的权值异或和$\text{xor}$上这个区间去重后的所有数的权值异或和为$0$。

然后我们从左到右枚举区间的右端点，然后维护每个左端点的权值。我们定义$pre[i]$为上一个与位置$i$上的数相等的位置，那么右端点移到$i$时，左端点在$[1,pre[i]]$的所有区间的权值都会异或上位置$i$上的数的权值。

然后我们就是需要支持区间$\text{xor}$一个数，查询有多少个$0$。这个东西显然可以用分块解决。

复杂度$O(n\sqrt{n})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 200000, maxv = 1000000, blksz = 500, mod = 100003;
int n, pre[maxn + 10], lst[maxv + 10];
ull w[maxv + 10], val[maxn + 10], tag[maxn / blksz + 10], ans;

struct hshtb {
    int h[mod], cnt[blksz + 10], ccnt, nxt[blksz + 10];
    ull val[blksz + 10];

    void clear() {
        for (int i = 1; i <= ccnt; ++i)
            h[val[i] % mod] = 0;
        ccnt = 0;
    }

    int& operator[] (ull v) {
        for (int i = h[v % mod]; i; i = nxt[i])
            if (val[i] == v) return cnt[i];
        val[++ccnt] = v; cnt[ccnt] = 0; 
        nxt[ccnt] = h[v % mod]; h[v % mod] = ccnt;
        return cnt[ccnt];
    }

    int ask(ull v) {
        for (int i = h[v % mod]; i; i = nxt[i])
            if (val[i] == v) return cnt[i];
        return 0;
    }
}mp[maxn / blksz + 10];


void modify(int p, ull v) {
    for (int i = 1; (i - 1) * blksz + 1 <= p; ++i)
        if (i * blksz <= p) tag[i] ^= v;
        else {
            for (int j = (i - 1) * blksz + 1; j <= i * blksz && j <= n; ++j) {
                val[j] ^= tag[i];
            }
            tag[i] = 0; mp[i].clear();
            for (int j = (i - 1) * blksz + 1; j <= i * blksz && j <= n; ++j) {
                if (j <= p) val[j] ^= v;
                ++mp[i][val[j]];
            }
        }
}

ull query(int p) {
    ull ans = 0;
    for (int i = 1; (i - 1) * blksz + 1 <= p; ++i)
        if (i * blksz <= p) ans += mp[i].ask(tag[i]);
        else for (int j = (i - 1) * blksz + 1; j <= p; ++j)
            ans += !(val[j] ^ tag[i]);
    return ans;
}

int main() {
    w[0] = 131;
    for (int i = 1; i <= maxv; ++i) {
        w[i] = w[i - 1];
        w[i] ^= w[i] << 13;
        w[i] ^= w[i] >> 17;
        w[i] ^= w[i] << 5;
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        ++mp[(i - 1) / blksz + 1][0];
    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        pre[i] = lst[x]; lst[x] = i;
        modify(pre[i], w[x]);
        ans += query(i);
    }
    printf("%llu", ans);
}