树状数组【CF703D】Mishka and Interesting sum

Description

给你n( 1<=n<=1000000)个数,以及m(1<=m<=1000000)个询问,每个询问包括l和r，问你在这n个数中，区间l~r，出现偶数个数的数的异或和

Input

第一行一个整数 n，表示数列的长度

接下来一行 n 个非负整数，表示 a 数组中的每个元素

接下来一行一个整数 m，表示查询的数量

接下来 m 行，每行两个整数 l, r 表示这次查询区间的左右端点

Output

对于每组查询，输出一行一个整数，表示这组查询的答案

刚看到题的一瞬间,输出出现偶数次的数的异或和.

"不是0嘛？这不sb题？"

突然发现看错题.

原来是求出现偶数次的单个数的异或和。

通过一些推导可以发现,答案是求区间内不同数的异或和与区间异或和的异或和。

为什么？

我们假设当前查询的区间的数为：\(1,3,4,2,5,4,1\)

此时根据异或的性质\(x\) ^\(x=0\),我们再异或上区间内不同的数。

则这段异或起来就是：\(1\)^\(4\)。

稍作解释一下

我们区间中出现偶数次的数的异或和就是\(0\)，此时再异或上区间内不同的数。

此时这些出现偶数次的数的异或再次出现。

而那些出现单次的数就消失了.

那么现在问题就变为维护区间内不同的数的异或和

这题数据范围的话,需要离散化。

因为没有修改操作,所以考虑离线.我们对右端点进行排序(从小到大)

然后考虑用一种数据结构维护：线段树 or 树状数组。

这里用了树状数组。

树状数组维护异或。

记录一下这个数上一个出现的位置.

然后遇到某个位置再出现,我们再在树状数组删去这个数几个(即再异或一次.)

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

const int gz=3000008;

inline void in(R int &x)

{

	R int f=1;x=0;R char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,a[gz],sum[gz],pre[gz],b[gz],head[gz];

int new_n=1,q,ans[gz];

struct cod

{

	int l,r,idx;

	bool operator <(const cod&a)const

	{

		return r<a.r;

	}

}que[gz];

#define lowbit(x) x&-x

int tr[gz<<1];

inline void add(R int o,R int del)

{

	for(;o<=n;o+=lowbit(o))

		tr[o]^=del;

}

inline int query(R int o)

{

	R int res=0;

	for(;o;o-=lowbit(o))

		res^=tr[o];

	return res;

}

int main()

{

	in(n);

	for(R int i=1;i<=n;i++)in(a[i]),b[i]=a[i];

	sort(b+1,b+n+1);

	for(R int i=2;i<=n;i++)

		if(b[new_n]!=b[i])b[++new_n]=b[i];

	for(R int i=1;i<=n;i++)

		a[i]=lower_bound(b+1,b+new_n+1,a[i])-b;

	for(R int i=1;i<=n;i++)

	{

		sum[i]=sum[i-1]^b[a[i]];

		pre[i]=head[a[i]];

		head[a[i]]=i;

	}

	in(q);

	for(R int i=1;i<=q;i++)

		in(que[i].l),in(que[i].r),que[i].idx=i;

	sort(que+1,que+q+1);

	R int now=1;

	for(R int i=1;i<=q;i++)

	{

		R int r=que[i].r,l=que[i].l;

		while(now<=r)

		{

			if(pre[now])

				add(pre[now],b[a[now]]);

			add(now,b[a[now]]);

			now++;

		}

		ans[que[i].idx]=(query(r)^query(l-1))^(sum[r]^sum[l-1]);

	}

	for(R int i=1;i<=q;i++)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

树状数组【CF703D】Mishka and Interesting sum

Description

Input

Output

最新文章

热门文章