[CQOI2018]异或序列

题目描述

已知一个长度为n的整数数列 a1,a2,...,an ,给定查询参数l、r,问在 al,al+1,...,ar 区间内,有多少子序列满足异或和等于k。也就是说,对于所有的x,y (I ≤ x ≤ y ≤ r),能够满足 axax+1...ay=k 的x,y有多少组。

输入输出格式

输入格式:

输入文件第一行,为3个整数n,m,k。

第二行为空格分开的n个整数,即 a1,a2,..an 。

接下来m行,每行两个整数 lj,rj ,表示一次查询。

输出格式:

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

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

说明

对于30%的数据, 1 ≤ n, m ≤ 1000

对于100%的数据, 1n,m105,0k,ai105,1ljrjn


经典的莫队

维护异或前缀和


 

发表评论