BZOJ4888 [Tjoi2017]异或和【树状数组】

题目链接

题解

要求所有连续异或和，转化为任意两个前缀和相减

要求最后的异或和，转化为求每一位\(1\)的出现次数

所以我们只需要对每一个\(i\)快速求出\(sum[i] - sum[j] \quad [j < i]\)当前位的\(1\)的个数

显然是将前\(i\)个数放到某一个数据结构中查询

我的思路到这里停住

两个数相减，要第\(b\)位为\(1\)，我们放到具体情境中观察：

假若\(sum[i]\)的第\(b\)位为\(1\)

....1....

....?....

1、如果\(?=0\)

就是

....1....

....0....

发现\(1\)后面的数大于等于 \(0\)后面的数，为此时相减后该位为\(1\)的充要条件

2、如果\(?=1\)

就是

....1....

....1....

发现\(sum[i]\)的\(1\)后面的数小于\(sum[j]\)的\(1\)后面的数，为此时相减后该位为\(1\)的充要条件

如果第\(b\)位为\(0\)也是类似的讨论

如果我们将该位为\(0\)和\(1\)的数分开讨论，现在问题就转化为了，如何快速求当前某一范围内的数的个数

显然就是对\(0\)和\(1\)分别开一个权值树状数组啦

题目中\(a[i]\)之和\(\le 10^6\)的条件也是一个明显的暗示

这样我们就用\(O(log_2(max\{a_i\}) * nlog\sum a_i) \approx O(nlog^2n)\)的时间复杂度做出这道题了

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define lbt(x) (x & -x)

using namespace std;

const int maxn = 100005,maxm = 1000005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int MX = 1000001;

struct BIT{

	int s[maxm];

	void clear(){cls(s);}

	void add(int u){while (u <= MX) s[u]++,u += lbt(u);}

	int query(int u){int re = 0; while (u) re += s[u],u -= lbt(u); return re;}

	int sum(int l,int r){return query(r) - query(l - 1);}

}T0,T1;

int n,a[maxn],mx;

bool check(int b){

	T0.clear(); T1.clear();

	LL cnt = 0; int tmp;

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

		tmp = a[i] % b + 1;

		if (a[i] & b){

			cnt += T0.sum(1,tmp) + T1.sum(tmp + 1,MX);

			T1.add(tmp);

		}

		else {

			cnt += T0.sum(tmp + 1,MX) + T1.sum(1,tmp);

			T0.add(tmp);

		}

	}

	return cnt & 1;

}

int main(){

	n = read(); int x,ans = 0;

	REP(i,n) a[i] = a[i - 1] + (x = read()),mx = max(mx,a[i]);

	for (int i = 0; mx; i++,mx >>= 1){

		if (check(1 << i)) ans += (1 << i);

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ4888 [Tjoi2017]异或和【树状数组】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ4888 [Tjoi2017]异或和 【树状数组】

题目链接

题解

最新文章

热门文章

BZOJ4888 [Tjoi2017]异或和【树状数组】