CodeForces 703D Mishka and Interesting sum

时间:2021-09-07 00:44:40

异或运算性质,离线操作,区间求异或和。

直接求区间出现偶数次数的异或和并不好算,需要计算反面。

首先,很容易求解区间异或和,记为$P$。

例如下面这个序列,$P = A[1]xorA[2]xorA[3]......xorA[15]$

$1$,$1$,$1$,$2$,$2$,$3$,$3$,$3$,$4$,$4$,$5$,$5$,$6$,$7$,$7$。

出现偶数次数的异或和记为$Q$,那么$Q = 2xor4xor5xor7$。

我们记$F=PxorQ$,如果知道$F$,那么就能计算出$Q$。所以接下来我们来看一下$F$是什么东西。

$F = 1xor1xor1xor2xor3xor3xor3xor4xor5xor6xor7 = 1xor2xor3xor4xor5xor6xor7$。

也就是说,$F$为区间去重之后的那些数的异或和。

那么,接下来问题变成了如何求解区间去重之后的数字的异或和。这个问题和$HDU3333$一模一样,只不过从$+$变成了$xor$。

$HDU3333$:$http://www.cnblogs.com/zufezzt/p/5805327.html$

求得了$F$之后,我们只需将$PxorF$,即可得到$Q$。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
} const int maxn=;
int T,n;
int a[maxn],c[maxn],sum[maxn],Ans[maxn];
struct X { int id,L,R;LL ans; }q[maxn]; bool cmp(X a,X b) { return a.R<b.R; }
bool cmp1(X a,X b) { return a.id<b.id; } int lowbit(int x) { return x&(-x); }
void update(int p,LL v)
{
while(p<=n) c[p]=c[p]^v,p=p+lowbit(p);
}
int XOR(int p)
{
int res=;
while(p>) res=res^c[p],p=p-lowbit(p);
return res;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-]^a[i];
map<int,int>m;
int Q; scanf("%d",&Q);
for(int i=;i<=Q;i++) scanf("%d%d",&q[i].L,&q[i].R),q[i].id=i;
sort(q+,q++Q,cmp); int p=;
for(int i=;i<=n;i++)
{
int h=m[a[i]];
if(h!=) update(h,a[i]); update(i,a[i]); m[a[i]]=i;
while(p<=Q&&q[p].R==i) q[p].ans=XOR(q[p].R)^XOR(q[p].L-), p++;
}
for(int i=;i<=Q;i++) Ans[q[i].id]=sum[q[i].R]^sum[q[i].L-]^q[i].ans;
for(int i=;i<=Q;i++) printf("%d\n",Ans[i]);
return ;
}