题解：P3760 [TJOI2017] 异或和

思路

问题就是求所有区间和的异或和，这种统计区间贡献问题不难想到分治，假设当前的分治区间为

[l,r]

，区间中点为

mid

，对

[l,mid]

的

a_i

做一遍后缀和得到

sml

，对

[mid+1,r]

的

a_i

做一遍前缀和得到

smr

，那么问题就转换成了求

\oplus_{i\in [l,mid]} \oplus_{j\in[mid+1,r]}(sml_i+smr_j)

。

首先容易想到按位拆贡献，只需对每个位

i

求出有多少个

sml_j+smr_k(j\le k)

使得其和的第

i

位上为

1

。

不妨舍去

i

位以后的位，那么

sml_j+smr_k

的范围就在

[0,2^i),[2^i,2^{i+1}),[2^{i+1},2^{i+1}+2^i),[2^{i+1}+2^i,2^{i+2})

其中之一，显然只有第

2,4

个区间有贡献，剩下的问题就是对于一个已知的

u

如何快速求出有多少个

j,k(j\le k)

使得

sml_j+smr_k\ge u

了，这是个经典的问题，排序双指针即可。

归并排序即可做到

\mathcal O(n\log V)

。

总时间复杂度就是

\mathcal O(n\log n\log V)

。

CPP

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e5+6;
int n;
int a[Maxn];
int b[Maxn],c[Maxn];
int sm[Maxn];

inline void mergesort(int t[],int l,int r,int i){
	int tot1=0,tot2=0;
	for(int j=l;j<=r;j++) 
		if(t[j]>>(i+1)&1) b[++tot1]=t[j]-(1<<(i+1)); 
		else c[++tot2]=t[j];
	merge(b+1,b+tot1+1,c+1,c+tot2+1,t+l);
}
inline int calc(int u,int L,int mid,int R){
    int r=R+1;int ret=0;
    for(int l=L;l<=mid;l++){
		while(sm[r-1]+sm[l]>=u and r-1>mid) --r;
		ret=ret^((R-r+1)&1);
	}
    return ret&1;
}

int solve(int l,int r){
	if(l>r) return 0;
	if(l==r) return a[l];
	int mid=l+r>>1,ret=0;
	sm[mid]=a[mid],sm[mid+1]=a[mid+1];
	for(int i=mid-1;i>=l;i--) sm[i]=sm[i+1]+a[i];
	for(int i=mid+2;i<=r;i++) sm[i]=sm[i-1]+a[i];

	sort(sm+l,sm+mid+1),sort(sm+mid+1,sm+r);
	for(int i=20;~i;i--){
		mergesort(sm,l,mid,i);
		mergesort(sm,mid+1,r,i);
        int u=1<<i;
        if((calc(u,l,mid,r)-calc(u*2,l,mid,r)+calc(u*3,l,mid,r))&1) ret^=(1<<i);
    }
	
	return solve(l,mid)^solve(mid+1,r)^ret;
}

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

	return 0;
}

题解：P3760 [TJOI2017] 异或和

文章操作

思路

相关推荐

评论

题解：P3760 [TJOI2017] 异或和