[数据结构与算法]数据结构补题

莫队

1.XOR and Favorite Number CodeForces - 617E

[题意]：
有一个数字 k 和一个长度为 n 的 a数组 。接下来有 m 次查询，每次查询会给出一对 [ L,R ] ,针对每一对L和R，求有多少对（ i , j ）,满足 L<=i<=j<=R 并且 ai ^ ai+1 ^… ^aj = k。

[思考]：
这道题目属于区间段异或和，所以我们容易想到用前缀和来处理，所以我们在输入的时候就可以将 a[i] 预处理为 前 i 项的前缀和。

我们使用莫队来优化查询。

如果当前已经求得的区间为 [curL , curR] ，当前区间内符合条件的答案为 num，定义一个数组 cnt，用于记录当前区间内存在的所有异或值的个数（区间在扩张的时候一直在计算），例如cnt[i] = 异或值为i的个数有 cnt[i] 个。

接下来我们来看区间扩张与收缩，以区间扩张为例，我们假定当前 右端点 curR 一定，左端点curL发生移动 ，那么我们所求的就是区间有多少个L，满足 a[curR] ^ a[L-1] =k， 等价于 a[L-1] = k^ a[curR] ，所以问题可以转化为 求 cnt[k^ a[curR]].

还有一点需要注意的是，因为对于每一个所求的 L,我们需要的是 a[L-1]，所以在移动左端点的时候我们进入 函数 del 和 add 的时候需要多 - 1；
除此之外，我们还需要注意 num 变化和 cnt数组变化的先后顺序，因为本题可能存在 x==x^k 的情况，而num 值变化所需要的是 cnt[x ^ k]， 所以需要处理掉 x 带来的影响，剩下的详见代码。

[代码实现]：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn= 3e6+100;
int n,q,k,a[maxn];//a[i]记录的是异或前缀和 
int curL,curR;
int len;
int st[maxn],ed[maxn],sz[maxn],blo[maxn];
ll cnt[maxn],ans[maxn];
ll num;
struct node{
	int l,r,id;
}que[maxn];
bool cmp(node a,node b){  //莫队的排序
	if(blo[a.l]!=blo[b.l]) return blo[a.l]<blo[b.l];
	return a.r<b.r;
}
void init(int n){ //分块初始化
	len=sqrt(n);
	for(int i=1;i<=len;i++){
		st[i]=n/len*(i-1)+1;
		ed[i]=n/len*i;
	}
	ed[len]=n;
	for(int i=1;i<=len;i++){
		for(int j=st[i];j<=ed[i];j++){
			blo[j]=i;
		}
	}
}
void add(int x){
	num+=cnt[a[x]^k]; //先加上 a[x]^k ，保证在 a[x]^k==a[x] 的情况下，cnt数组的是没有因为当前a[x] 进行错误更新
	cnt[a[x]]++;
}
void del(int x){
	cnt[a[x]]--; //当 a[x]^k==x ，因为cnt数组中已经包含了 a[x]，所以需要将其先行减去，阻止它干扰 a[x]^k 的值
	num-=cnt[a[x]^k];
}
int main(){
	scanf("%d%d%d",&n,&q,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]^=a[i-1];
	init(1100000);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&que[i].l,&que[i].r);
		que[i].id=i;
	}
	sort(que+1,que+1+q,cmp);
	curL=1;
	cnt[0]++;
	for(int i=1;i<=q;i++){
		while(curL<que[i].l) del(curL-1),curL++; //处理左端点移动的时候需要多减去1
		while(curL>que[i].l) add(curL-2),--curL;
		while(curR<que[i].r) add(++curR);
		while(curR>que[i].r) del(curR--);
		ans[que[i].id]=num;
	}
	for(int i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}