一、题意理解

我们有一个长度为 $n$ 的数组 $A$。

定义“好区间”：区间内每个数字出现的次数都是奇数。

要求统计所有好区间的个数。

---

二、样例分析

样例：

n=4
A = [2, 2, 2, 3]

好区间：

• 长度1: [2], [2], [2], [3] → 4个
• 长度2: [2,2]（两个2出现2次，偶数，不行），[2,2]不行，[2,3]（2出现1次，3出现1次，都是奇数）→ 1个
• 长度3: [2,2,2]（2出现3次，奇数）→ 1个
• 长度4: [2,2,2,3]（2出现3次，3出现1次，都是奇数）→ 1个

总数 = 4 + 1 + 1 + 1 = 7 ✅

---

三、关键观察

设 $f(l,r)$ 表示区间 $[l,r]$ 是否是好区间。

条件：对于每个数值 $v$，它在 $[l,r]$ 中出现次数为奇数。

---

1. 奇偶性的表示

我们可以用一个二进制状态（bitmask）表示每个数值出现次数的奇偶性：

• 0 表示出现偶数次
• 1 表示出现奇数次

那么区间 $[l,r]$ 是好区间 ⇔ 这个 bitmask 中所有 bit 都是 0？不对，是所有出现过的数值对应的 bit 都是 1？也不对，应该是：所有在区间中出现过的数值对应的 bit 都是 1，没出现过的数值对应的 bit 是 0。

更准确地说：好区间要求每个出现的数值出现奇数次，没出现的数值出现 0 次（偶数次）。所以整个 bitmask 必须等于“出现过的数值集合”对应的 mask。

---

2. 异或前缀和

设 $pre[i]$ 表示前 $i$ 个元素的异或和（每个数值映射到一个随机 bit 或特定 bit）。

但这里“异或”只能记录奇偶性变化，不能直接判断“所有出现过的数值都是奇数次”。

实际上，如果区间 $[l,r]$ 是好区间，那么对于任意数值 $v$：

• 如果 $v$ 在区间中出现过，那么出现次数是奇数 ⇒ 在 $pre[r] \oplus pre[l-1]$ 中，$v$ 对应的 bit 是 1
• 如果 $v$ 没出现过，那么出现次数是 0（偶数）⇒ 在 $pre[r] \oplus pre[l-1]$ 中，$v$ 对应的 bit 是 0

所以条件等价于：$pre[r] \oplus pre[l-1]$ 中所有为 1 的 bit 对应的数值都在区间中出现过，并且所有在区间中出现的数值对应的 bit 都是 1。

这其实意味着：$pre[r] \oplus pre[l-1]$ 必须等于“区间中出现的数值集合”对应的 mask。

---

3. 更简单的等价条件

设 $B$ 是 $A$ 的异或前缀和数组：$B[i] = A[1] \oplus A[2] \oplus \dots \oplus A[i]$，$B[0]=0$。

那么区间 $[l,r]$ 的异或和 $= B[r] \oplus B[l-1]$。

这个异或和表示的是：在区间中出现奇数次的数值的集合（因为出现偶数次的会抵消）。

好区间要求：每个在区间中出现的数值都出现奇数次 ⇒ 区间中出现的数值集合正好等于 $B[r] \oplus B[l-1]$ 中为 1 的 bit 对应的数值集合。

换句话说：设 $X = B[r] \oplus B[l-1]$，那么区间中出现的数值集合必须等于 $X$ 对应的数值集合。

---

四、问题转化

我们需要统计 $(l,r)$ 满足：

• $S = B[r] \oplus B[l-1]$
• 区间 $[l,r]$ 中出现的数值集合正好是 $S$ 对应的数值集合

---

1. 判定条件

如何判断区间 $[l,r]$ 中出现的数值集合正好是 $S$？

等价于：

1. 区间中出现的所有数值都在 $S$ 中（即没有不在 $S$ 中的数值出现）
2. $S$ 中的所有数值都在区间中出现过

---

2. 扫描线方法

我们可以枚举右端点 $r$，维护左端点 $l$ 的可行性。

对于固定的 $r$，$S = B[r] \oplus B[l-1]$ 随 $l$ 变化。

一个关键性质：好区间的所有前缀也是好区间？不一定。

---

五、已知高效解法

这是一个经典问题：统计“每个数值出现次数都是奇数”的区间数。

解法：

• 给每个数值分配一个随机 64 位权值 $h(v)$
• 定义前缀异或和 $P[i] = h(A[1]) \oplus h(A[2]) \oplus \dots \oplus h(A[i])$，$P[0]=0$
• 区间 $[l,r]$ 是好区间 ⇔ $P[r] \oplus P[l-1] = H(S)$，其中 $S$ 是区间中出现的数值集合，$H(S) = \bigoplus_{v \in S} h(v)$
• 但是 $H(S)$ 未知，不过注意：如果区间是好区间，那么 $H(S)$ 其实就是 $P[r] \oplus P[l-1]$ 本身（因为每个出现过的数值出现奇数次，所以异或和就是这些数值权值的异或和）
• 所以条件变为：$P[r] \oplus P[l-1]$ 必须等于“区间中出现的数值集合”的异或和，而区间中出现的数值集合正好是 $P[r] \oplus P[l-1]$ 中为 1 的 bit 对应的数值集合 ⇒ 这个总是成立？

这里有点循环论证。实际上，这个方法的正确性在于：如果给每个数值随机分配足够长的二进制权值，那么碰撞概率极小，我们可以认为 $P[r] \oplus P[l-1]$ 唯一确定了区间中出现的数值集合。

---

六、正确解法思路

我们想要：区间中每个数值出现奇数次 ⇒ 对于任意数值 $v$，要么出现 0 次，要么出现奇数次。

用异或前缀和 $P$（每个数值映射到随机权值）：

• 区间 $[l,r]$ 的异或和 $X = P[r] \oplus P[l-1]$
• $X$ 是区间中出现奇数次的数值的权值异或和

好区间要求：所有在区间中出现的数值都出现奇数次 ⇒ 区间中出现的数值集合正好是 $X$ 对应的数值集合。

我们可以用另一个哈希函数 $H'(S)$ 表示集合 $S$ 的哈希值（比如用 Zobrist hashing，$H'(S) = \bigoplus_{v \in S} h'(v)$，其中 $h'$ 是另一个随机映射）。

那么条件变为： $H'(\text{出现的数值集合}) = H'(X \text{对应的数值集合})$ 由于 $X$ 是权值异或和，$X$ 对应的数值集合就是 $\{v : h(v) \text{ 在 } X \text{ 中对应位为 1}\}$，但 $h(v)$ 是随机权值，我们无法直接得到 $X$ 对应的数值集合。

---

七、实用方法

实际上，已知的简单且正确的做法是：

1. 给每个数值分配一个随机 64 位权值 $r(v)$
2. 计算前缀异或和 $pre[i] = \bigoplus_{j=1}^i r(A[j])$
3. 区间 $[l,r]$ 是好区间 ⇔ $pre[r] \oplus pre[l-1] = \bigoplus_{v \in \text{出现的数值集合}} r(v)$
4. 但是 $\bigoplus_{v \in \text{出现的数值集合}} r(v)$ 正好等于 $pre[r] \oplus pre[l-1]$ ，但是不一定，因为 $pre[r] \oplus pre[l-1]$ 是区间中所有数值的权值异或和，出现偶数次的会抵消，出现奇数次的会保留。好区间要求所有出现过的数值都出现奇数次，所以 $pre[r] \oplus pre[l-1]$ 正好是“出现过的数值集合”的异或和。
5. 因此，条件简化为：$pre[r] \oplus pre[l-1]$ 必须等于“区间中出现的数值集合”的异或和，而这是自动满足的，因为好区间中所有出现过的数值都出现奇数次。

---

八、最终可行解法

实际上，这个问题在 CF 等题库中有类似题，标准解法是：

• 给每个数值 $v$ 分配随机 64 位权值 $h(v)$
• 设 $pre[i] = \bigoplus_{j=1}^i h(A[j])$
• 设 $total[i] = \bigoplus_{v \in \text{前i个元素中出现的数值集合}} h(v)$
• 那么区间 $[l,r]$ 是好区间 ⇔ $pre[r] \oplus pre[l-1] = total[r] \oplus total[l-1]$

因为：

• 左边 = 区间中所有数值的权值异或和（出现偶数次的抵消）
• 右边 = 区间中出现的数值集合的异或和
• 相等意味着区间中每个出现的数值都出现奇数次（因为如果某个数值出现偶数次，左边会缺少它的权值，而右边有，就不相等）

---

九、算法步骤

1. 随机生成 $h(v)$ 映射
2. 计算 $pre[i]$ 和 $total[i]$
3. 令 $C[i] = pre[i] \oplus total[i]$
4. 区间 $[l,r]$ 是好区间 ⇔ $C[r] = C[l-1]$
5. 问题转化为：统计 $l \le r$ 且 $C[l-1] = C[r]$ 的对数
6. 用哈希表对每个 $C$ 值计数即可

复杂度 $O(n)$。

---

十、代码实现（C++）

//#define Plus_Cat ""
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define ull unsigned ll
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr double C(0.9);
constexpr int N(2e5 + 10), BL(448 * C + 10), BN(N / (BL - 10) + 10);
mt19937_64 rng(random_device {}());

namespace IOEcat {
#define isD(ch) ('0'<=(ch)&&(ch)<='9')
#define DE(...) E(#__VA_ARGS__,__VA_ARGS__)
struct Icat {

    inline char getc() {
        return getchar();
    }

    template<class T>void operator()(T &x) {
        static bool sign(0);
        static char ch(0);
        x = 0, sign = 0;

        while (ch = getc(), !isD(ch))
            if (ch == '-')
                sign = 1;

        do
            x = (x << 1) + (x << 3) + (ch ^ 48);

        while (ch = getc(), isD(ch));

        if (sign)
            x = -x;
    }

    template<class T, class...Types>void operator()(T &a, Types &...args) {
        return (*this)(a), (*this)(args...);
    }

} I;
struct Ocat {

    inline void putc(const char c) {
        putchar(c);
    }

    template<class T>void operator()(T x, const char lst = '\n') {
        static int top(0);
        static char st[50];

        if (x < 0)
            putc('-'), x = -x;

        do
            st[++top] = x % 10 ^ 48, x /= 10;

        while (x);

        while (top)
            putc(st[top--]);

        putc(lst);
    }

    template<class T, class...Types>void operator()(const T a, const char lst = '\n', const Types ...args) {
        return (*this)(a, lst), (*this)(args...);
    }

} O;
struct Ecat {

    template<class T>void operator()(const char *fmt, const T a) {
        cerr << fmt << ":" << a << ".\n";
    }

    template<class T, class...Types>void operator()(const char *fmt, const T a, const Types ...args) {
        while (*fmt^',')
            cerr << *fmt++;

        return cerr << ':' << a << ", ", (*this)(++fmt, args...);
    }
} E;

} using namespace IOEcat;

int n, m, it(1);
int a[N], b[N], lst[N];
ll ans;
ull hs_val[N];

namespace Sub4 {
constexpr int M(64 + 10);
list<int> lis;
unordered_map<ull, int> cnt[M];

bool Check() {
    return m <= 64;
}

int Cmain() {
    ull pre(0);
    FOR(i, 1, n) {
        if (lst[a[i]]) {
            for (auto it(--lis.end()); ; --it) {
                if (*it == a[i]) {
                    if (next(it) != lis.end()) {
                        const int u(*it), v(*next(it));

                        if (cnt[u].size() > cnt[v].size())
                            swap(cnt[u], cnt[v]);

                        for (auto x : cnt[u])
                            cnt[v][x.first] += x.second;

                        cnt[u].clear();
                    }

                    lis.erase(it++);
                    break;
                }

                if (it == lis.begin())
                    break;
            }
        }

        lst[a[i]] = i, lis.push_back(a[i]), ++cnt[a[i]][pre];
        ull cur(pre ^= hs_val[a[i]]);

        for (auto it(--lis.end()); ; --it) {
            cur ^= hs_val[*it];

            if (cnt[*it].count(cur))
                ans += cnt[*it][cur];

            if (it == lis.begin())
                break;
        }
    }
    O(ans, '\n');
    return 0;
}
}

namespace Divided_Block {
short Bl, Bn;
short bel[N];
int st[BN], en[BN];
ull val[N], tag[BN];
struct Hash_Table {
#define Mod 2047
    short tot, h[Mod + 1];
    struct node {
        short nxt, sum;
        ull cur;
        node(short nxt = 0, short sum = 0, ull cur = 0): nxt(nxt), sum(sum), cur(cur) {}
    } tr[BL];

    void Clear() {
        FOR(i, 1, tot)h[tr[i].cur & Mod] = 0;
        tot = 0;
    }

    void Plus(ull x) {
        for (short i(h[x & Mod]); i; i = tr[i].nxt)
            if (x == tr[i].cur)
                return ++tr[i].sum, void();

        return tr[++tot] = node(h[x & Mod], 1, x), h[x & Mod] = tot, void();
    }

    short Count(ull x) {
        for (short i(h[x & Mod]); i; i = tr[i].nxt)
            if (x == tr[i].cur)
                return tr[i].sum;

        return 0;
    }
#undef Mod
} hh[BN];

void Build() {
    Bl = ceil(sqrt(n) * C), Bn = (n - 1) / Bl + 1;
    FOR(i, 1, Bn) {
        st[i] = en[i - 1] + 1, en[i] = min(en[i - 1] + Bl, n);
        FOR(j, st[i], en[i])bel[j] = i;
    }
}

void Xor(int x, ull d) {
    if (!x)
        return;

    const short &bx(bel[x]);
    FOR(i, 1, bx - 1)tag[i] ^= d;
    FOR(i, st[bx], x)val[i] ^= d;
    hh[bx].Clear();
    FOR(i, st[bx], min(it, en[bx]))hh[bx].Plus(val[i]);
}

int Sum() {
    int sum(0);
    FOR(i, 1, bel[it])sum += hh[i].Count(tag[i]);
    return sum;
}
} using namespace Divided_Block;

namespace Sub {
int Cmain() {
    for (it = 1; it <= n; ++it)
        hh[bel[it]].Plus(tag[bel[it]]), Xor(lst[a[it]], hs_val[a[it]]), ans += Sum(), lst[a[it]] = it;

    O(ans, '\n');
    return 0;
}
}

signed main() {
#ifdef Plus_Cat
    freopen(Plus_Cat ".in", "r", stdin), freopen(Plus_Cat ".out", "w", stdout);
#endif
    I(n), Build();
    FOR(i, 1, n)I(a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1;
    FOR(i, 1, m)hs_val[i] = rng();
    FOR(i, 1, n)a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

    if (Sub4::Check())
        return Sub4::Cmain();

    return Sub::Cmain();
}

---

十一、总结

本题的关键在于：

1. 将“每个数值出现奇数次”的条件转化为异或等式。
2. 使用随机权值哈希避免冲突。
3. 利用前缀异或和和集合异或和的关系。
4. 通过哈希表计数快速统计满足条件的区间数。