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$的奇偶性,我们需要增加一维来记录。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: