2016-09-27

NEUOJ 1454 逃票的chanming(1【树状数组】

题目链接：

http://acm.neu.edu.cn/hustoj/problem.php?id=1454

题意：

给定序列长度$n$，两种操作，一是子序列所有元素与$x$异或，二是输出子序列所有元素异或和。
数据范围:$0 \le N,M \le 500000,0 \le v \le 2^{30}$

分析：

首先分析异或操作的性质：偶数个$x相异或=0$，奇数个$x相异或=x$.
假设我们从位置$x$开始对元素进行了修改（异或一个其他数），那么对于$x$后面与$x$奇偶性相同的位置$y$，在求区间$[x,y]$的异或和的时候答案需要异或一个$x$，而与$x$奇偶性不同的区间异或和不发生改变。
利用上述性质，我们可以使用树状数组实现单点更新和单点查询，而在更新的时候考虑到$x$的奇偶性，我们需要增加一维来记录。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 500000 + 5;
typedef long long ll;
int bit[2][maxn];
void Add(int x, int val) 
{
	for (int i = x; i < maxn; i += i & (-i)) {
		bit[x & 1][i] ^= val;
	}
}
int Query(int x)
{
	int res = 0;
	for(int i = x; i; i -= i & (-i)){
		res ^= bit[x & 1][i];
	}
	return res;
}
int main (void)
{
	int n, m;scanf("%d%d", &n, &m);
	int a, b, dt, s;
	memset(bit, 0 ,sizeof(bit));
	for(int i = 0; i < m; ++i){
		scanf("%d", &s);
		if(s == 0){
			scanf("%d%d%d", &a, &b, &dt);	
			Add(a, dt);
			Add(b + 1, dt); 
		}else{
			scanf("%d%d", &a, &b);
			if(a > b) swap(a, b);
			printf("%d\n", Query(b) ^ Query(a - 1));
		}
	}
	return 0;
}