Codeforces 703D Mishka and Interesting sum

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n , (1 \leq n \leq 1000000)\)个数字，\(m, (1 \leq m \leq 1000000)\)个查询，每次查询输出\(l_i\)到\(r_i\)中出现偶数次的数字的异或和。

思路

出现偶数次的数字的异或和等于整个区间的异或和与区间不相同的数字的异或和。整个区间的异或和可以用前缀和在\(O(1)\)的时间查询，区间不相同数字的异或和可以数状数组在\(O(logn)\)的时间查询。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int maxn = 1000010;
int n, m, num;
int a[maxn], ans[maxn];
int sum[maxn], bit[maxn];
int Hash[maxn], last[maxn];

struct query {
  int l, r, id;
  bool operator < (const query& rhs) const {
    return r < rhs.r;
  }
} q[maxn];

inline int lowbit(int i) {
  return i & -i;
}

int Sum(int i) {
  int res = 0;
  while (i > 0) {
    res ^= bit[i];
    i -= lowbit(i);
  }
  return res;
}

void Update(int i, int x) {
  while (i <= n) {
    bit[i] ^= x;
    i += lowbit(i);
  }
}

int& Last(int x) {
  return last[lower_bound(Hash, Hash + num, x) - Hash];
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    Hash[i - 1] = a[i];
    sum[i] = sum[i - 1] ^ a[i];
  }
  sort(Hash, Hash + n);
  num = int(unique(Hash, Hash + n) - Hash);
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    q[i].id = i;
    scanf("%d%d", &q[i].l, &q[i].r);
  }
  sort(q, q + m);
  int p = 0;
  for (int i = 1; i <= n; ++i) {
    int& k = Last(a[i]);
    if (k != 0) {
      Update(k, a[i]);
    }
    Update(k = i, a[i]);
    while (p < m && q[p].r == i) {
      ans[q[p].id] = sum[i] ^ sum[q[p].l - 1] ^ Sum(i) ^ Sum(q[p].l - 1);
      ++p;
    }
  }
  for (int i = 0; i < m; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
相关文章