题意

给定一个长度为 $n\le 2\times 10^5$ 的正整数序列，满足所有数不大于 $10^6$ 。定义一个连续的好子序列为：该子序列中不同数出现的次数均为奇数。求这个序列的好子序列个数。

思路

一般来说求一个序列的所有满足条件子序列，如果无法线性时间内做，就先考虑分治，然后每次找横跨中点的合法区间的个数。最终加和即为所求。一般结合二维数点扫描线可以做到 $O(n\log^2 n)$ 的复杂度。CSP202112-5 极差路径 就是把序列搬到树上，然后用点分治+二维数点的应用。

但是本题这种出现频率奇数，实在不好维护可加性，所以分治应该是不行了，但是分块还是可以用的。

一般来说，出现频率均为奇数，我们可以转到异或上面。其出现次数为奇数，意味着这个子序列所有数的异或和等于子序列中出现过的不同数的异或和。这个东西我们可以采用类似 HH 的项链 的方式做扫描线的维护和判断。

但是由于每个数太过紧凑，直接异或不可行，我们可以利用随机化哈希的思想，给 $1\sim 10^6$ 的每一个数都再赋一个随机权值，让上面的异或在随机权值下进行运算。这样就可以以极小的错误率避免冲突，快速进行异或判等。

设 $s_i$ 为 $a_1,…,a_i$ 对应权值的异或前缀和，$b_{[l,r]}$ 是 $a_l,…,a_r$ 当中不同数的权值异或和。

于是对于满足条件的 $[l,r]$ 有： $s_r\oplus s_{l-1}=b_{[l,r]}$ ，再转一下就变成 $s_r=b_{[l,r]}\oplus s_{l-1}$ 。于是对于每一个 $r$ ，我们去找 $l\in [1,r]$ 当中，有多少个满足 $s_{l-1}\oplus b_{[l,r]}$ 与 $s_r$ 相等即可。为了方便查询，我们可以直接把所有的 $b$ 初始就设为 $s_{l-1}$ 。

那么我们在维护的时候，核心就是每次丢入 $a_r$ 时，有多少个 $b_{[l,r]}$ 会受到影响？这个就看前面 HH 的项链一题即可。我们对每一个数记录他上一次出现的次数 $lst_i$ ，那么丢入一个 $r$ 之后，相当于左端点的 $[lst_{a_r}+1,r]$ 都要增异或一个 $a_r$ 。

然后我们维护的时候就直接分块维护，每个块内维护一个哈希表。为了保证常数，建议手写链式前向星。由于每个块内元素个数很小，且哈希可以使用较小质数，所以可以用 short 优化常数。

分块维护的操作较为基础，每个块需要对应一个异或懒标记，当需要修改散块的时候，则下放懒标记，然后暴力清空哈希表并重新加入。修改整块就放在懒标记上。查询哈希值等于某值的个数时同理，查询散块则先下放重构然后暴力查询，查询整块时则先异或懒标记之后再在哈希表里面查频率。

最终时间复杂度是 $O(n\sqrt n)$ ，最大的两个点跑了 1.1s 。

typedef long long i64;

const int N = 200010, V = 1000000, B = 455;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<i64> gen_num(0, 2147483647);

struct hashmap
{
    static const short M = 10003;

    i64 key[B];
    short val[B], nxt[B], h[M];
    short cnt;
    inline short find(i64 k)
    {
        short id = k % M;
        for (short i = h[id]; i; i = nxt[i]) if (key[i] == k) return i;
        return 0;
    }
    inline void add(i64 k)
    {
        short hit = find(k), id = k % M;
        if (hit) ++val[hit];
        else key[++cnt] = k, val[cnt] = 1, nxt[cnt] = h[id], h[id] = cnt;
    }
    inline short query(i64 k) 
    {
        short hit = find(k);
        return hit ? val[hit] : 0;
    }
    inline void clr() { memset(h, 0, sizeof(h)), cnt = 0; }
};
// random hashcode
int n, blk, bn, a[N];
int lst[V + 10];
inline i64 gen_hash() { return (gen_num(rng) << 31) | gen_num(rng); }
i64 ha[V + 10];
// block hashmap
int L[B], R[B], no[N];

i64 bsum[N], tag[B], xsum[N]; // xor prefixsum
hashmap mp[B];

inline void build()
{
    blk = std::max((int)sqrt(n), 1), bn = (n / blk) + (n % blk != 0);
    for (int i = 1; i <= n; ++i) no[i] = (i - 1) / blk + 1;
    for (int i = 1; i <= bn; ++i) L[i] = (i - 1) * blk + 1, R[i] = std::min(i * blk, n);
}
inline void rebuild(int u)
{
    mp[u].clr(); // clear and pushdown
    for (int i = L[u]; i <= R[u]; ++i) bsum[i] ^= tag[u], mp[u].add(bsum[i]);
    tag[u] = 0;
}
inline void update(int l, int r, i64 v)
{
    if (no[l] == no[r])
    {
        for (int i = l; i <= r; ++i) bsum[i] ^= v;
        rebuild(no[l]);
    }
    else
    {
        for (int i = l; i <= R[no[l]]; ++i) bsum[i] ^= v;
        for (int i = L[no[r]]; i <= r; ++i) bsum[i] ^= v;
        rebuild(no[l]), rebuild(no[r]);
        for (int i = no[l] + 1; i < no[r]; ++i) tag[i] ^= v;
    }
}
inline int query(int l, int r, i64 v)
{
    int ret = 0;
    if (no[l] == no[r])
    {
        rebuild(no[l]);
        for (int i = l; i <= r; ++i) ret += (bsum[i] == v);
    }
    else
    {
        rebuild(no[l]), rebuild(no[r]);
        for (int i = l; i <= R[no[l]]; ++i) ret += (bsum[i] == v);
        for (int i = L[no[r]]; i <= r; ++i) ret += (bsum[i] == v);
        for (int i = no[l] + 1; i < no[r]; ++i) ret += mp[i].query(v ^ tag[i]);
    }
    return ret;
}

int main()
{
    n = rd();
    for (int i = 1; i <= V; ++i) ha[i] = gen_hash();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    build();
    for (int i = 1; i <= n; ++i) bsum[i] = xsum[i - 1], xsum[i] = xsum[i - 1] ^ ha[a[i]];
    for (int i = 1; i <= bn; ++i) rebuild(i);
    i64 ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        update(lst[a[i]] + 1, i, ha[a[i]]), lst[a[i]] = i;
        ans += query(1, i, xsum[i]);
    }
    printf("%lld", ans);
}