P4462「[CQOI2018]异或序列」

1. 题目

题目链接:P4462「[CQOI2018]异或序列」

题目描述

已知一个长度为n的整数数列 a1,a2,,ana_1,a_2,\cdots,a_n,给定查询参数 l,rl,r,问在 al,al+1,,ara_l,a_{l+1},\cdots,a_r 区间内,有多少子序列满足异或和等于 kk。也就是说,对于所有的 x,yx,ylxyrl \leq x \leq y \leq r),能够满足 axax+1ay=ka_x \bigoplus a_{x+1} \bigoplus \cdots \bigoplus a_y = kx,yx,y 有多少组。

输入格式

输入文件第一行,为 33 个整数 n,m,kn,m,k

第二行为空格分开的 nn 个整数,即 a1,a2,..ana_1,a_2,..a_n

接下来 mm 行,每行两个整数 lj,rjl_j,r_j,表示一次查询。

输出格式

输出文件共 mm 行,对应每个查询的计算结果。

输入输出样例

输入 #1

1
2
3
4
5
6
7
4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

输出 #1

1
2
3
4
5
4
2
1
2
1

说明/提示

对于 30%30\% 的数据,1n,m10001 \leq n, m \leq 1000

对于 100%100\% 的数据,1n,m105,0k,ai105,1ljrjn1 \leq n, m \leq 10^5, 0 \leq k, a_i \leq 10^5,1 \leq l_j \leq r_j \leq n

2. 题解

分析

  • 首先需要了解异或运算的优美性质。
  1. si=a1a2ais_i = a_1 \bigoplus a_2 \bigoplus \cdots \bigoplus a_i,则有

alal+1ar=sl1sr{\begin{array}{c} a_l \bigoplus a_{l+1} \bigoplus \cdots \bigoplus a_r = s_{l-1} \bigoplus s_r \end{array}}

  1. 假设 ab=ca \bigoplus b = c,则有

a=bcb=ac{\begin{array}{c} a = b \bigoplus c \\ b = a \bigoplus c \\ \end{array}}

因此,对于原题,我们可以将其转换为:在区间 [l,r][l,r] 内,有多少对 sx1,sys_{x-1},s_ylxyrl \leq x \leq y \leq r)满足 sx1sy=ks_{x-1} \bigoplus s_y = k,其中,si=a1ai1s_i = a_1 \bigoplus \cdots \bigoplus a_{i-1},即 ss 数组为 aa 数组的异或前缀和。

  • 然后计算一下时间复杂度,O(mn)O(m\sqrt{n}) 可以过,而且可以离线查询,因此可以考虑用莫队算法。接下的问题就是如何实现相邻查询区间的 O(1)O(1) 转移。

假设序列 ss 的长度为 nn,若已知 [l,r][l,r] 区间的答案为 ansl,rans_{l,r},且 countcount 数组记录了数组 ss[l,r][l,r] 区间中各个数的出现次数,则区间 [l,r+1][l,r+1](其它三个相邻区间的分析类似)的答案为

ansl,r+1=ansl,r+count[s[r+1]k]{\begin{array}{c} ans_{l,r+1} = ans_{l,r} + count[s[r+1]^k] \end{array}}

因此,只要在区间改变时维护好 countcount 数组,就可实现相邻查询区间 O(1)O(1) 复杂度的转移。

注意

需要判断一下应该开的数组大小以及数据类型是否会溢出:

  • 数组大小:由于 0k,ai1050 \leq k, a_i \leq 10^5,因此它们之间的异或结果最大为 2log2105+112^{\lfloor\log_2{10^5}\rfloor + 1} - 1,即异或的结果会超出 10510^5,但始终能用 log2105\lfloor\log_2{10^5}\rfloor 位二进制表示。而 log2105\lfloor\log_2{10^5}\rfloor 位二进制所能表示的最大数为 2log2105+112^{\lfloor\log_2{10^5}\rfloor + 1} - 1,又 2log2105+112×10512^{\lfloor\log_2{10^5}\rfloor + 1} - 1 \leq 2 \times 10^5 - 1,因此数组长度需要开到 2×1052 \times 10^5 才合适。
  • 数据类型:由于区间 [l,r][l,r] 中最多有 Crl+12C_{r-l+1}^2 种两两配对,且 rl+1105r-l+1 \leq 10^5,因此 Crl+12<=5×104×(1051)5×109C_{r-l+1}^2 <= 5 \times 10^4 \times (10^5 - 1) \approx 5 \times 10^9,所以 int 数据类型其实是不够用的,要用 long long

虽然这道没有卡这两点,但不可忽略它们。另一道基本相同的题 CF617E XOR and Favorite Number 就考虑了这两点。

代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
using namespace std;

#ifndef _MOBK_
#define _MOBK_
#define ll long long
#define il inline
#define re register
#define MAXN 200100

char buf[200];

il ll read() {
ll x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}

il void write(ll x) {
ll cnt = 0;
while(x || !cnt) {
buf[cnt++] = (x%10) + 48;
x /= 10;
}
while(cnt) {
putchar(buf[--cnt]);
}
putchar('\n');
}

// 分块大小
ll bz;
// 莫队
struct MOBK {
// 查询区间
struct Query {
ll l, r, idx;
bool operator < (const Query q) const {
return l/bz != q.l/bz ? l < q.l :
(l/bz) & 1 ? r < q.r : r > q.r;
}
};
ll n, m; // 数列长度,查询次数
ll curans; // 当前查询答案
ll count[MAXN]; // 计数数组
ll result[MAXN]; // 答案数组(具体问题具体分析)
Query query[MAXN]; // 查询区间数组
// 初始化
MOBK() {
curans = 0;
memset(count, 0, sizeof(count));
memset(query, 0, sizeof(query));
}
MOBK(int _n, int _m): n(_n), m(_m) {
bz = (ll)sqrt(n);
curans = 0;
memset(count, 0, sizeof(count));
memset(query, 0, sizeof(query));
}
// 区间长度增一
il void add(ll x, ll k) {
curans += count[x^k];
++count[x];
}
// 区间长度减一
il void del(ll x, ll k) {
--count[x];
curans -= count[x^k];

}
// 求解答案
void solver(ll *a, ll k) {
sort(query, query+m);
re ll l = query[0].l;
re ll r = query[0].l-1;
for(re ll i = 0; i < m; ++i) {
while(r < query[i].r) {
add(a[++r], k);
}
while(r > query[i].r) {
del(a[r--], k);
}
while(l < query[i].l) {
del(a[l++], k);
}
while(l > query[i].l) {
add(a[--l], k);
}
result[query[i].idx] = curans;
}
for(ll i = 0; i < m; ++i) {
write(result[i]);
}
}
};
#endif

int main()
{
ll n = read();
ll m = read();
ll k = read();
static ll a[MAXN] = {0};
static MOBK mobk = MOBK(n, m);
for(re ll i = 1; i <= n; ++i) {
a[i] = read();
}
for(re ll i = 2; i <= n; ++i) {
a[i] ^= a[i-1];
}
for(re ll i = 0; i < m; ++i) {
mobk.query[i].l = read() - 1;
mobk.query[i].r = read();
mobk.query[i].idx = i;
}
mobk.solver(a, k);
return 0;
}