【线段树维护区间异或】codeforces E. XOR on Segment
2021-07-27 19:19:00 # ACM

题链

对于一个区间有如下数字{$5$，$6$，$7$，$8$}，他们的二进制表示分别为：

1
2
3
4
5：0101
6：0110
7：0111
8：1000

那么这区间数的总和可以这么计算：
$1*(2^3) + 3*(2^2) + 2*(2^1) + 2*(2^0)$;
其中$(2^i)$次方前的系数就是第$i$位的$1$的个数之和

将他们异或上一个值 如 $4$：

1
2
3
4
5^4: 0101^0100 = 0001
6^4: 0110^0100 = 0010
7^4: 0111^0100 = 0011
8^4: 1000^0100 = 1100

那么异或后这一段区间的总和为：
$1*(2^3) + 1*(2^2) + 2*(2^1) + 2*(2^0)$;
发现对比异或之前就只有(2^2)前的系数改变；
原因是$4$的二进制表示为$0100$, 只有$(2^2)$的系数为$1$；
所以对于需要异或的一个值$x$，如果$x$的第$i$位为$1$，那么这个区间内的第$i$位的$1$的个数就需要变化；
变化的结果就是区间长度减去第$i$位$1$的个数；
于是可以开$20$棵线段树维护每一位的结果；

代码段我对于一个节点开了个数组，就不搞个$20$棵了，本质上是一样的；

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 1000000007 
#define MAXN 100000
#define MXLEN 17
#define MS 100009

int n,m;
struct node{
	int cnt[22];
	int la[22];
	bool isla;
}p[MS<<2];

void push_up(int rt){
	for(int i=20;i>=0;i--){
		p[rt].cnt[i] = p[ls].cnt[i] + p[rs].cnt[i];
	}
}

void build(int l,int r,int rt){
	if(l == r){
		int x;
		cin >> x;
		for(int i=20;i>=0;i--){
			p[rt].cnt[i] = ( (x>>i)&1 );
		}
		return;
	}
	int m = l+r>>1;
	build(l,m,ls); build(m+1,r,rs);
	push_up(rt); 
}

void push_down(int rt,int l,int r){
	if(p[rt].isla){
		int m = l+r>>1;
		int ln = m-l+1;
		int rn = r-m;
		p[ls].isla = p[rs].isla = false;
		for(int i=20;i>=0;i--){
			int t = p[rt].la[i];
			p[rt].la[i] = 0;
			if(t){
				p[ls].cnt[i] = ln - p[ls].cnt[i];
				p[rs].cnt[i] = rn - p[rs].cnt[i];
			}
			p[ls].la[i] ^= t;
			p[rs].la[i] ^= t;
			if(p[ls].la[i]) p[ls].isla = true;
			if(p[rs].la[i]) p[rs].isla = true;
		}
		p[rt].isla = false;
	}
}

void modify(int L,int R,int l,int r,int rt,int x){
	if(L <= l && r <= R){
		int sum = r-l+1;
		p[rt].isla = false;
		for(int i=20;i>=0;i--){
			int t = (x>>i)&1;
			if(t) p[rt].cnt[i] = sum-p[rt].cnt[i];
			p[rt].la[i] ^= t;
			if(p[rt].la[i]) p[rt].isla = true;
		}
		return;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	if(m >= L) modify(L,R,l,m,ls,x);
	if(m <  R) modify(L,R,m+1,r,rs,x);
	push_up(rt);
}

LL query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		LL sum = 0;
		for(int i=20;i>=0;i--){
			LL t = p[rt].cnt[i];
			sum += (1ll<<i)*t;
		}
		return sum;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	LL ans = 0;
	if(m >= L) ans += query(L,R,l,m,ls);
	if(m <  R) ans += query(L,R,m+1,r,rs);
	return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    build(1,n,1);
    cin >> m;
    for(int i=1;i<=m;i++){
    	int op,l,r,x;
		cin >> op >> l >> r;
		if(op == 1){
			cout << query(l,r,1,n,1) << "\n";
		}
		else if(op == 2){
			cin >> x;
			modify(l,r,1,n,1,x);
		}
	}
    
    
    return 0;
}
Prev
2021-07-27 19:19:00 # ACM
Next