#P5301. [Cqoi2018]异或序列

    ID: 1740 传统题 1000ms 512MiB 尝试: 561 已通过: 322 难度: 6 上传者: 标签>难度分类提高位运算异或前缀和离线与分治普通莫队奇偶块排序模拟与实现技巧增量维护CF2000鸣谢Amphetamine整理题面&&codeforces617E

[Cqoi2018]异或序列

[CQOI2018] 异或序列

题目描述

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

输入格式

从标准输入读入。第一行三个整数 n,m,kn,m,k。

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

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

输出格式

向标准输出写出 mm 行,每行一个整数,表示对应查询的子区间数量。

样例 #1

样例输入 #1

4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

样例输出 #1

4
2
1
2
1

提示

对于 30%30\% 的数据,1≤n,m≤10001 \leq n, m \leq 1000。

对于 100%100\% 的数据,1≤n,m≤1051 \leq n, m \leq 10^5,0≤k,ai≤1050 \leq k, a_i \leq 10^5,1≤lj≤rj≤n1 \leq l_j \leq r_j \leq n。