1. 题目
题目链接：P4462「[CQOI2018]异或序列」 。
题目描述
输入格式
输出格式
输出文件共 mmm 行，对应每个查询的计算结果。
输入输出样例
输入 #1
代码语言：javascript复制4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4输出 #1
代码语言：javascript复制4
2
1
2
1说明/提示
2. 题解
分析
- 首先需要了解异或运算的优美性质。
注意
需要判断一下应该开的数组大小以及数据类型是否会溢出：
虽然这道没有卡这两点，但不可忽略它们。另一道基本相同的题 CF617E XOR and Favorite Number 就考虑了这两点。
代码
代码语言：javascript复制#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) 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;
}
