题解 P2826 【[USACO08NOV]光开关Light Switching】
斯德哥尔摩
2017-10-14 08:19:00
看到题目就应该想到了 线段树 了吧。。。（虽说标签中也有。。。）
线段树 应该都会。。。
每个节点存 某一范围内所有1的个数 。
具体看注释吧。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1//左孩子
#define RSON rt<<1|1//右孩子
#define DATA(x) a[x].data//节点值
#define SIGN(x) a[x].c//懒惰标记
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r//左右区间
#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)//区间范围
#define MAXN 100010
using namespace std;
int n,m;
struct node{
int data,c;
int l,r;
}a[MAXN<<2];//线段树 数组，切记，一定要开 4 倍空间，不然会炸。。。
inline int read(){//弱弱的读入优化。。。
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void pushup(int rt){//数值上传
DATA(rt)=DATA(LSON)+DATA(RSON);//每个节点（叶节点除外）的值 = 左孩子的值 + 右孩子旳值
}
void pushdown(int rt){//标记下传
if(!SIGN(rt)||LSIDE(rt)==RSIDE(rt))
return;
SIGN(LSON)^=SIGN(rt);////处理左孩子。取反，从1变为0 或 从0变为1
DATA(LSON)=WIDTH(LSON)-DATA(LSON);//区间范围 = 区间内0的个数 + 区间内1的个数，移项即可。。。
SIGN(RSON)^=SIGN(rt);//处理右孩子
DATA(RSON)=WIDTH(RSON)-DATA(RSON);
SIGN(rt)=0;//标记清空
}
void buildtree(int l,int r,int rt){//建树
int mid;
LSIDE(rt)=l;
RSIDE(rt)=r;//这两句是建树的核心之一
if(l==r){
DATA(rt)=0;
return;
}
mid=l+r>>1;
buildtree(l,mid,LSON);
buildtree(mid+1,r,RSON);//这是核心之二
pushup(rt);
}
void update(int l,int r,int rt){//修改
int mid;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r){//如果该节点在范围内，则 处理 并 返回
SIGN(rt)^=1;
DATA(rt)=WIDTH(rt)-DATA(rt);//已解释过。。。见 标记下传
return;
}
pushdown(rt);//一定要先下传，再递归
mid=LSIDE(rt)+RSIDE(rt)>>1;//分为 左孩子 与 右孩子，分别处理
if(l<=mid)update(l,r,LSON);
if(mid<r)update(l,r,RSON);
pushup(rt);//一定要上传
}
long long query(int l,int r,int rt){
int mid;
long long ans=0;
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)//如果该节点在范围内
return DATA(rt);//返回节点值
pushdown(rt);//下传标记
mid=LSIDE(rt)+RSIDE(rt)>>1;//分为 左孩子 与 右孩子，分别求和
if(l<=mid)ans+=query(l,r,LSON);
if(mid<r)ans+=query(l,r,RSON);
return ans;//不要忘记返回值。。。
}
int main(){
int f,x,y;
n=read();m=read();
buildtree(1,n,1);
while(m--){
f=read();x=read();y=read();
if(f==0)update(x,y,1);//分类
if(f==1)printf("%lld\n",query(x,y,1));
}
return 0;//终于结束。。。
}
```