CF703D Mishka and Interesting sum 题解

题目链接：Mishka and Interesting sum

题意：

给定 $n$ 个数的序列 $a$。$m$ 次操作。操作有一种：

• l r：求 $a_l\sim a_r$ 中，出现偶数次的数的异或和（每个数只算一次）。

数据范围：

$1\le n,m\le 10^6$，$1\le a_i\le 10^9$。

「出现偶数次的数的异或和」显然等于「出现的所有数的异或和」异或上「出现奇数次的数的异或和」

「出现奇数次的数的异或和」直接预处理前缀和就好了（偶数的会抵消，奇数的也只会留下一个）。

现在我们要统计「出现的所有数的异或和」，考虑用树状数组维护，做法类似于经典的 HH 的项链。

大概操作就是，先对数离散化，然后询问离线（按右端点升序排序），维护一个指针 $r$ ，一路扫过去

扫的过程中记录每个数的出现位置 $c_x$ ，比如现在是 $x$ ，位置为 $i$ ，那么将 $c_x$ 的贡献在树状数组上去掉

再把 $i$ 的位置加上 $x$ 的贡献，然后令 $c_x \gets i$ ，这样树状数组区间查询就能维护区间内的答案了。

时间复杂度 $\mathcal{O}(q \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

struct node { int l, r, id; } q[N];
int n, a[N], b[N], c[N], sum[N], tr[N], ans[N];
#define lowbit(x) ((x) & (-(x)))
void add(int x, int v) { for(int i = x; i && i <= n; i += lowbit(i)) tr[i] ^= v; }
int qry(int x, int r = 0) { for(int i = x; i > 0; i -= lowbit(i)) { r ^= tr[i]; } return r; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 1, n) { cin >> a[i]; b[i] = a[i]; sum[i] = sum[i - 1] ^ a[i]; }
    int m; cin >> m; sort(b + 1, b + 1 + n); 
    rep(i, 1, n) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
    rep(i, 1, m) { cin >> q[i].l >> q[i].r; q[i].id = i; }
    sort(q + 1, q + 1 + m, [](node a, node b) { return a.r < b.r; });
    rep(i, 1, m)
    {
        static int r = 1;
        for(; r <= q[i].r; ++r) { add(c[a[r]], b[a[r]]); c[a[r]] = r; add(c[a[r]], b[a[r]]); }
        ans[q[i].id] = qry(q[i].l - 1) ^ qry(q[i].r) ^ sum[q[i].r] ^ sum[q[i].l - 1];
    }
    rep(i, 1, m) cout << ans[i] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/w2i52jha