题解 P2846【光开关】
这道题是练习线段树的优秀入门题，切掉他说明你对算法的理解程度已经不止局限于模板。
灯只有亮，暗两种状态，可以用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的艺术