luogu3760 [TJOI2017]异或和

看这里

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, s[100005], a[100005], c[2][1000005], ans;

int lb(int x){

	return x&-x;

}

void add(int x, int p){

	if(p==0)	c[x][0]++;

	else

		for(int i=p; i<=1000000; i+=lb(i))

			c[x][i]++;

}

int query(int x, int p){

	int re=0;

	for(int i=p; i; i-=lb(i))

		re += c[x][i];

	return re+c[x][0];

}

int main(){

	cin>>n;

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

		scanf("%d", &s[i]);

		s[i] += s[i-1];

	}

	for(int i=0; i<20; i++){

		int cnt=0, now=0;

		memset(c, 0, sizeof(c));

		add(0, 0);

		for(int j=1; j<=n; j++){

			int tmp=s[j]&(1<<i);

			if(tmp)	cnt = query(1, 1000000) - query(1, a[j]) + query(0, a[j]);

			else	cnt = query(0, 1000000) - query(0, a[j]) + query(1, a[j]);

			add(tmp>0, a[j]);

			if(cnt&1)	now ^= 1;

			a[j] |= tmp;

		}

		if(now)	ans |= 1<<i;

	}

	cout<<ans<<endl;

	return 0;

}

巴特西

luogu3760 [TJOI2017]异或和

最新文章

热门文章