个人认为比较好理解的线段树代码

因为是异或，并且只有1 和 0 两个状态，所以每次区间异或后，我们只需要把该区间0的数量和1的数量交换一下就好了。

另外注意pushdown是cg（change）需要每次异或一下，单纯的赋值会出现这种问题：

1^1=0     1^1^1=1
而单纯赋值，则会变成1^1^1出现0的情况。

另外没什么问题，很好的一道线段树题目

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
//头文件您就自己写吧 

#define lson i*2,l,mid
#define rson i*2+1,mid+1,r
#define ls i*2
#define rs i*2+1

using namespace std;

int n,m,a[200500];

struct tree{
	int l,r,ope,clo,cg;
}t[800400];

void build_tree(int i,int l,int r)
{
	t[i].l=l;
	t[i].r=r;
	if(l==r) 
	{
		t[i].clo=!a[l];  //由于只有0 1两种状态 ！0=1 
		t[i].ope=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build_tree(lson);
	build_tree(rson);
	t[i].clo=t[ls].clo+t[rs].clo;
	t[i].ope=t[ls].ope+t[rs].ope;
	return ;
}

void pushdown(int i)
{
	if(!t[i].cg) return ;
	t[i].cg=0;
	t[ls].cg^=1;   //记得标记下传 异或两次==不异或 
	t[rs].cg^=1;
	swap(t[ls].clo,t[ls].ope);
	swap(t[rs].clo,t[rs].ope);
}

void change_tree(int i,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		t[i].cg^=1;
		swap(t[i].ope,t[i].clo);  //交换一下就好了 
		return ;	
	}
	pushdown(i);
	int mid=(l+r)/2;
	if(x<=mid) change_tree(lson,x,y);
	if(y>mid) change_tree(rson,x,y);
	t[i].clo=t[ls].clo+t[rs].clo; //每次pushdown记得加上这句话 
	t[i].ope=t[ls].ope+t[rs].ope;
	return ;
}

int ask_ope_tree(int i,int l,int r,int x,int y)
{
	if(l>=x&&r<=y) return t[i].ope;
	pushdown(i);
	int mid=(l+r)/2;
	int ans=0;
	if(x<=mid) ans+=ask_ope_tree(lson,x,y);
	if(y>mid) ans+=ask_ope_tree(rson,x,y);
	t[i].clo=t[ls].clo+t[rs].clo;  //这段话记得加上 
	t[i].ope=t[ls].ope+t[rs].ope;
	return ans;
}

int main()
{
	int i,j;
	scanf("%d %d\n",&n,&m);  //记得读入空格 
	for(i=1;i<=n;i++)
	{
		char t1;
		scanf("%c",&t1);
		a[i]=t1-'0';
	}
	build_tree(1,1,n);
	for(i=1;i<=m;i++)
	{
		int t1,t2,t3;
		scanf("%d %d %d",&t1,&t2,&t3);
		if(t1==0) change_tree(1,1,n,t2,t3);
		else printf("%d\n",ask_ope_tree(1,1,n,t2,t3));
	}
	return 0;
}