题解 - [BZOJ 5301] [LOJ 2534] [Luogu P4462] [CQOI2018] 异或序列

发表于 更新于 分类于 ， 本文字数： 192 阅读时长 ≈ 1 分钟

题面

题解

一句话题意：查询区间内子区间异或和为一定值的个数

暴力: \(O(n^3m)\) (查询:\(O(m)\), 枚举子序列: \(O(n^2)\), 计算异或和: \(O(n)\))

优化:

  1. \(\Rightarrow O(n^2m)\): 前缀和 (计算异或和: \(O(n)\Rightarrow O(1)\))

    令

    \[ s_i:=\bigoplus_{i=1}^x a_i \]

    则

    \[ \bigoplus_{i=l}^r a_i=s_{l-1}\oplus s_r \]

  2. \(\Rightarrow O(nm)\): 莫队

    • 转换思路

      注意到

      \[ a\oplus b=c\iff a\oplus c=b \]

      用一个桶 cnt[x] 记录当前区间内 s[i]=x 的个数

      则当前区间的结果为 \(\displaystyle\sum_{i=l}^r\mathrm{cnt}_{s_i\oplus k}\)

  3. \(\Rightarrow O(n\min\{m,\sqrt n\})\): 奇偶化排序优化

代码

Show code

Luogu_P4462view raw
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
#define _for(i, l, r) for (auto i = (l); i <= (r); ++i)
namespace FastIO {
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
int p, p3 = -1;
int getc() {
  return p1 == p2 &&
             (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ?
           EOF :
           *p1++;
}
void read() {}
void print() {}
template <typename T, typename... T2>
void read(T &x, T2 &...oth) {
  int f = 0;
  x = 0;
  char ch = getc();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    ch = getc();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getc();
  }
  if (f) x = -x;
  read(oth...);
}
void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; }
template <typename T, typename... T2>
void print(T x, T2... oth) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = hh;
  print(oth...);
}
template <typename T>
void print_h(T x, char h) {
  if (p3 > 1 << 20) flush();
  if (x < 0) buf2[++p3] = 45, x = -x;
  do { a[++p] = x % 10 + 48; } while (x /= 10);
  do { buf2[++p3] = a[p]; } while (--p);
  buf2[++p3] = h;
}
void putchar(char a) { buf2[++p3] = a; }
}  // namespace FastIO
using FastIO::print;
using FastIO::read;
const int M = 2e5 + 5;
const int N = 1e5 + 5;
int n, m, sqrt_n, blocks[N];
i64 k;
i64 xor_num[N];
struct query_node {
  int l, r, id;
  bool operator<(const query_node &other) const {
    return (blocks[l] != blocks[other.l]) ? l < other.l :
                                            (r > other.r) ^ (blocks[l] & 1);
  }
} query[N];
i64 ans[N];
namespace mo {
i64 cnt[M];
i64 add(int p) {
  i64 ans = cnt[xor_num[p] ^ k];
  ++cnt[xor_num[p]];
  return ans;
}
i64 del(int p) {
  --cnt[xor_num[p]];
  return cnt[xor_num[p] ^ k];
}
}  // namespace mo
using mo::add;
using mo::del;
int main() {
  read(n, m, k);
  sqrt_n = sqrt(n);
  _for(i, 1, n) blocks[i] = (i - 1) / sqrt_n + 1;
  _for(i, 1, n) {
    read(xor_num[i]);
    xor_num[i] ^= xor_num[i - 1];
  }
  for (int i = 1, l, r; i <= m; ++i) {
    read(l, r);
    query[i] = {l - 1, r, i};
  }
  std::sort(query + 1, query + m + 1);
  int l = 1, r = 0;
  i64 now_ans = 0;
  _for(i, 1, m) {
    int now_l = query[i].l, now_r = query[i].r;
    while (l < now_l) now_ans -= del(l++);
    while (l > now_l) now_ans += add(--l);
    while (r < now_r) now_ans += add(++r);
    while (r > now_r) now_ans -= del(r--);
    ans[query[i].id] = now_ans;
  }
  _for(i, 1, m) print(ans[i]);
  FastIO::flush();
  return 0;
}