CQOI2018 异或序列

wjh15101051's space

卧薪尝胆，厚积薄发。

CQOI2018 异或序列

Date: Sun Nov 18 08:44:05 CST 2018

In Category: NoCategory

Description：

一个长度为 $n$ 的整数数列，给定查询参数 $l,r$ ，问在 $[l,r]$ 区间内，有多少子区间满足异或和等于 $k$ 。

$1\leqslant n,m\leqslant 10^5$

Solution：

肯定是莫队，刚开始自己想了一个非常不可做的方法，然后看了题解发现先做一个前缀和，然后求的就是 $[l-1,r]$ 中前缀和相等的有几对，直接莫队就好了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 100010

int a[MAXN];

int pos[MAXN];

struct query

{

	int l,r,id;

	long long ans;

}q[MAXN];

bool cmp(query a,query b){return (pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l]);}

bool cmp_id(query a,query b){return a.id < b.id;}

int cnt[MAXN];

int s[MAXN];

long long res = 0;

void inc(int p)

{

	++cnt[s[p]];

	res += cnt[s[p] ^ k];

	return;

}

void dec(int p)

{

	res -= cnt[s[p] ^ k];

	--cnt[s[p]];

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)s[i] = s[i - 1] ^ a[i];

	int blo = sqrt(n);

	for(int i = 1;i <= n;++i)pos[i] = (i - 1) / blo + 1;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&q[i].l,&q[i].r);

		--q[i].l;

		q[i].id = i;

	}

	sort(q + 1,q + 1 + m,cmp);

	for(int i = 1,l = 1,r = 0;i <= m;++i)

	{

		for(;r < q[i].r;++r)inc(r + 1);

		for(;l > q[i].l;--l)inc(l - 1);

		for(;r > q[i].r;--r)dec(r);

		for(;l < q[i].l;++l)dec(l);

		q[i].ans = res;

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)

	{

		printf("%lld\n",q[i].ans);

	}

	return 0;

}

In tag: 数据结构-莫队

wjh15101051