【洛谷P2846】光开关【线段树】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P2846
给出一个01串，每次有两种操作：

• $0\ x\ y$，表示将$x$到$y$之间全部取反。
• $1\ x\ y$，表示输出$x$到$y$之间1的个数。

---

思路：

首先，这是一道三倍经验题。
P2574 XOR的艺术
P3870 [TJOI2009]开关
（这两道题可以用分块做，但是光开关用分块会T）

---

这道题其实就是一个裸的线段树。用$tree[x].l$和$tree[x].r$表示这个区间的左右端点，$tree[x].num$表示这个区间有多少个1，$tree[x].lazy$就是懒惰标记。
其中只有$tree[x].lazy$和线段树模板不一样。由于很明显如果我们将同一个区间取反两次，那么就是没有取反的意思。所以，$tree[x].lazy$其实只要表示这个区间是否被按了奇数次就可以了（按偶数次其实就是按很多个两次，依旧没变），所以$tree[x].lazy$的取值就只会是0或1（0表示按了偶数次，1表示按了奇数次），每次更新时异或1即可。
时间复杂度：$O(nlogn)$

---

分块的做法也稍微提一下。可以将这个总区间分成$\sqrt{n}$个小区间，每次直接在每个小区间内更新，与分块模板也很像。
时间复杂度：$O(n\sqrt{n})$

---

线段树模板：https://blog.csdn.net/SSL_ZYC/article/details/81045174
分块模板：https://blog.csdn.net/SSL_ZYC/article/details/81978158

---

代码：

#include <cstdio>
#define N 1000100
using namespace std;

int n,m,w,x,y;

struct node
{
	int l,r,lazy,num;
}tree[N*3];

void make(int x) 
{
	if (tree[x].l==tree[x].r) return;
	int mid=(tree[x].l+tree[x].r)/2;
	tree[x*2].l=tree[x].l;
	tree[x*2].r=mid;
	tree[x*2+1].l=mid+1;
	tree[x*2+1].r=tree[x].r;
	make(x*2);
	make(x*2+1);
}

void pushdown(int x)  //下传标记
{
	if (tree[x].lazy)
	{
		tree[x*2].num=tree[x*2].r-tree[x*2].l+1-tree[x*2].num;
		tree[x*2].lazy^=1;
		tree[x*2+1].num=tree[x*2+1].r-tree[x*2+1].l+1-tree[x*2+1].num;
		tree[x*2+1].lazy^=1;
		tree[x].lazy=0;
	}
}

int ask(int x,int l,int r)  //查找
{
	if (tree[x].l==l&&tree[x].r==r) return tree[x].num;
	if (tree[x].l==tree[x].r) return 0;
	pushdown(x);
	int mid=(tree[x].l+tree[x].r)/2;
	if (l>mid) return ask(x*2+1,l,r);
	if (r<=mid) return ask(x*2,l,r);
	return ask(x*2,l,mid)+ask(x*2+1,mid+1,r);
}

void change(int x,int l,int r)  //修改
{
	if (tree[x].l==l&&tree[x].r==r)
	{
		tree[x].num=tree[x].r-tree[x].l+1-tree[x].num;  //更新每个区间的值
		tree[x].lazy^=1;
		return;
	}
	if (tree[x].l==tree[x].r) return;
	pushdown(x);
	int mid=(tree[x].l+tree[x].r)/2;
	if (l>mid)
	{
		change(x*2+1,l,r);
		tree[x].num=tree[x*2].num+tree[x*2+1].num;  //更新每个区间的值
		return;
	}
	if (r<=mid)
	{
		change(x*2,l,r);
		tree[x].num=tree[x*2].num+tree[x*2+1].num;  //更新每个区间的值
		return;
	}
	change(x*2,l,mid);
	change(x*2+1,mid+1,r);
	tree[x].num=tree[x*2].num+tree[x*2+1].num;  //更新每个区间的值
}

int main()
{
	scanf("%d%d",&n,&m);
	tree[1].l=1;
	tree[1].r=n;
	make(1);
	while (m--)
	{
		scanf("%d%d%d",&w,&x,&y);
		if (w)
		{
			printf("%d\n",ask(1,x,y));
		}
		else
		{
			change(1,x,y);
		}
	}
	return 0;
}