正题

题目链接:https://www.luogu.com.cn/problem/CF1322B

题目大意

给出\(n\)个数字\(a_i\)求

\[\bigoplus _{i=1}^n\bigoplus _{j=i+1}^n(a_i+a_j)
\]

\(1\leq n\leq 4\times 10^5,1\leq a_i\leq 10^7\)

解题思路

分位考虑的话，先把每个位置更高位的给去掉，此时两个数字和这位为\(1\)的情况当且仅当他们的和在\([2^k,2^{k+1})\)或者\([2^{k+1}+2^k,2^{k+2})\)这两个区间。

双指针扫两次就好了。

时间复杂度\(O(n\log a_i)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=4e5+10;

ll n,a[N],b[N],sum;

signed main()

{

	scanf("%lld",&n);

	for(ll i=1;i<=n;i++)

		scanf("%lld",&b[i]);

	for(ll k=0;k<25;k++){

		ll l=1,r=0,ans=0;

		for(ll i=1;i<=n;i++)

			a[i]=b[i]&((1ll<<k+1)-1);

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

		for(ll i=n;i>=1;i--){

			ll L=(1ll<<k)-a[i],R=(1ll<<k+1)-a[i];

			while(r<n&&a[r+1]<R)r++;

			while(l<=n&&a[l]<L)l++;

			if(l>=i)break;

			ans+=min(r,i-1)-l+1;

		}

		l=1,r=0;

		for(ll i=n;i>=1;i--){

			ll L=(1ll<<k+1)+(1ll<<k)-a[i],R=(1ll<<k+2)-a[i];

			while(r<n&&a[r+1]<R)r++;

			while(l<=n&&a[l]<L)l++;

			if(l>=i)break;

			ans+=min(r,i-1)-l+1;

		}

		sum+=(ans&1)*(1ll<<k);

	}

	printf("%lld\n",sum);

	return 0;

}

巴特西

CF1322B-Present【双指针】

正题

题目大意

解题思路

code

最新文章

热门文章