自动搬运

查看原文

来自洛谷，原作者为

	Liu_zj 绿名了QWQ

搬运于2025-08-24 21:42:13，当前版本为作者最后更新于2019-07-15 09:27:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题是练习线段树的优秀入门题，切掉他说明你对算法的理解程度已经不止局限于模板。

灯只有亮，暗两种状态，可以用0,1表示。那么怎样让0变成1,1变成0呢？

我们选择XOR（异或）。符号是^，属于二进制运算符的一种。作用与名称相似，“异”即为1，“同”即为0。1^1=0,1^0=1,0^0=1。 我们发现，只要将0或1异或1就可以完成0、1的转换。

询问区间的亮灯的数量，所以线段树维护亮灯的数量。一个区间只有亮灯和灭灯，所以异或之后区间亮灯的数量就是异或前区间灭灯的数量。 即

if异或
区间亮灯数=区间灯总数-区间亮灯数

区间修改需要懒标记（lazy），我们又一次惊奇地发现，区间修改两次等于没有修改，与灯的状态相似，所以lazy的变化也可以用异或。

在具体的代码实现中，由于所有的灯开始都是灭的，所以省去了建树的操作。

码风清奇

#include<bits/stdc++.h>
using namespace std;
int lz[1000001];//懒标记
long long sum[1000001];//区间亮灯和
void update(int now)
{
	sum[now]=sum[now<<1]+sum[now<<1|1];//大区间的亮灯和等于左右区间的亮灯和的和。。。
}
void pushdown(int now,int l,int r)//标记下传
{
	int mid=(l+r)>>1;
	if(lz[now]==1)
	{
		lz[now<<1]^=1;//lz的改变用异或
		lz[now<<1|1]^=1;
		sum[now<<1]=(mid-l+1-sum[now<<1]);//区间灯数-亮灯数
		sum[now<<1|1]=(r-mid-sum[now<<1|1]);
		lz[now]=0;
	}
}
void change(int now,int l,int r,int lgo,int rgo)//区间修改
{
	if(l>=lgo&&r<=rgo)//如果当前区间（l,r）在修改区间（lgo,rgo）中
	{
		lz[now]^=1;//lz异或
		sum[now]=(r-l+1-sum[now]);
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(now,l,r);//别忘了标记下传
	if(lgo<=mid)
	change(now<<1,l,mid,lgo,rgo);
	if(rgo>mid)
	change(now<<1|1,mid+1,r,lgo,rgo);
	update(now);//修改后更新
}
long long find(int now,int l,int r,int lgo,int rgo)//区间查询
{
	long long ans=0;
	if(l>=lgo&&r<=rgo)//如果当前区间（l,r）在查询区间（lgo,rgo）中
		return sum[now];//返回值
	int mid=(l+r)>>1;
	pushdown(now,l,r);//标记下传double
	if(lgo<=mid)
	ans+=find(now<<1,l,mid,lgo,rgo);
	if(rgo>mid)
	ans+=find(now<<1|1,mid+1,r,lgo,rgo);
	return ans;
}
int main()
{
	int n,m,c,a,b;
	cin>>n>>m;//不必建树
	for(int i=1;i<=m;i++)
	{
		cin>>c>>a>>b;
		if(c==0)
			change(1,1,n,a,b);
		if(c==1)
			cout<<find(1,1,n,a,b)<<endl;
	}
}

做完这道题可以水一下双倍经验题目

P3870 [TJOI2009]开关

这道题需要建树

P2574 XOR的艺术