CF703D Mishaka and Interesting sum

Posted on Edited on In Word count in article: 506 Reading time ≈ 2 mins.
数据结构

CF703D Mishka and Interesting sum

题目大意:

给定一个序列, 有\(m\)次询问

每次询问会给你一个\([l, r]\), 让你求区间内出现偶数次的数的异或和

思路:

首先我们可以想到异或的某些性质:\(x\otimes y \otimes x = y\)

那么我们可以转化一下题目的意思, 我们可以先求一次区间的异或和, 再去异或一个东西, 可能就是我们想要的答案了

那么抑或什么呢, 按照由题意, 要异或一个能让奇数变成偶数的东西, 简单地说, 就是异或这个区间所有出现的数的异或和, 而并非整个区间的异或和

那么这个就和\(\text{HH}\)的项链有点类似了

时间复杂度就是一个\(O(n\log 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
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

int a[maxn], sum[maxn], ans[maxn];
int n, m, cnt, tree[maxn];
int __prev[maxn], __last[maxn];
map <int, int> T;

struct Node
{
    int l, r, id;
    bool operator < (const Node & T) const {
        return r < T.r;
    }
}Que[maxn];

inline void Update(int p, int val) 
{
    while (p <= n) {
        tree[p] ^= val;
        p += lowbit(p);
    }
}

inline int Query(int p)
{
    int ans(0);
    while (p) {
        ans ^= tree[p];
        p -= lowbit(p);
    }
    return ans;    
}

inline int Query(int l, int r)
{
    return Query(r) ^ Query(l - 1);
}

signed main()
{
    n = __read();
    for (int i(1); i <= n; i++) {
        a[i] = __read();
        if (!T[a[i]]) T[a[i]] = ++cnt;
        int p = T[a[i]];
        __last[i] = __prev[p];
        __prev[p] = i;
        sum[i] = sum[i - 1] ^ a[i];
    }
    m = __read();
    for (int i(1); i <= m; ++i)
        Que[i].l = __read(), Que[i].r = __read(), Que[i].id = i;
    sort (Que + 1, Que + m + 1);
    int p(1);
    for (int i(1); i <= m; ++i) {
        while (p <= Que[i].r) {
            if (__last[p]) Update(__last[p], a[p]);\\确保这个数只有一次的贡献
            Update(p, a[p]);
            ++p;
        }
        ans[Que[i].id] = Query(Que[i].l, Que[i].r) ^ sum[Que[i].r] ^ sum[Que[i].l - 1];
    }
    for (int i(1); i <= m; ++i) printf ("%d\n", ans[i]);
    system("pause");
}