题目

经典开关灯问题

思路

• tree 存的是什么

关是 $0$ 开是 $1$

现在有 $5$ 个数,假设开灯的数量是 $sum=2$

那么全部取反后,开灯数量就是 $5-sum$

• lazy 存的是什么

求和的线段树存的是需要更改的次数

那么现在这道题是求取反的次数

所以每次取反, lazy 的数值也跟着取反

细节

因为初始化为 $0$ ,所以不需要写建树初始化

与求和的线段树相比,更新函数不需要传入更改值

代码

#include<iostream>
#define N 100005
using namespace std;
int n,m;
int tree[4*N];
int lazy[4*N];
int gtree(int l,int r,int s,int t,int x)
{
	if(l<=s && t<=r)
		return tree[x];
	int m=(s+t)>>1,sum=0;
	if(lazy[x])
	{
		tree[x*2]=(m-s+1)-tree[x*2];
		tree[x*2+1]=(t-m)-tree[x*2+1];
		lazy[x*2]=!lazy[x*2];
		lazy[x*2+1]=!lazy[x*2+1];
		lazy[x]=0;
	}
	if(l<=m)
		sum+=gtree(l,r,s,m,x*2);
	if(r>m)
		sum+=gtree(l,r,m+1,t,x*2+1);
	return sum;
}
void utree(int l,int r,int s,int t,int x)
{
	if(l<=s && t<=r)
	{
		tree[x]=(t-s+1)-tree[x];
		lazy[x]=!lazy[x];
		return;
	}
	int m=(s+t)>>1;
	if(lazy[x] && s!=t)
	{
		tree[x*2]=(m-s+1)-tree[x*2];//左树的取反
		tree[x*2+1]=(t-m)-tree[x*2+1];//右树的取反
		lazy[x*2]=!lazy[x*2];
		lazy[x*2+1]=!lazy[x*2+1];
		lazy[x]=0;
	}
	if(l<=m)
		utree(l,r,s,m,x*2);
	if(r>m)
		utree(l,r,m+1,t,x*2+1);
	tree[x]=tree[x*2]+tree[x*2+1];
}
signed main()
{
	cin>>n>>m;
	while(m--)
	{
		int o,l,r;
		cin>>o>>l>>r;
		if(o==0)
			utree(l,r,1,n,1);
		else
			cout<<gtree(l,r,1,n,1)<<"\n";
	}
	return 0;
}