http://www.elijahqi.win/archives/547 题目描述 现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，……，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：
http://www.elijahqi.win/archives/547
题目描述
现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，……，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：第一种操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开），第二种操作是指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。
输入输出格式
输入格式：
第一行有两个整数N和M，分别表示灯的数目和操作的数目。接下来有M行，每行有三个整数，依次为：c, a, b。其中c表示操作的种类，当c的值为0时，表示是第一种操作。当c的值为1时表示是第二种操作。a和b则分别表示了操作区间的左右边界（1 ≤ a ≤ b ≤ N）。
输出格式：
每当遇到第二种操作时，输出一行，包含一个整数：此时在查询的区间中打开的灯的数目。
输入输出样例
输入样例#1：
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
输出样例#1：
1
2
可怜的我昨天因为这个一看是线段树，就直接按照染色来做了，其实应该取反，计算数目的时候应该用整体，减去当前的数目
tree[x].f表示是否覆盖的标记false 表示还没有下放需要下放，true表示下放过了 实际上下放的应该都是反转操作而不是染色操作 一定要^1因为我有可能对这一段反复修改 假如再对当前相同一段就行操作，那么就不用下放了，下放答案反而错误
#include<cstdio>#define N 110000
inline int read(){
int x=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch<='9'&&ch>='0') {x=x*10+ch-'0';ch=getchar();}
return x;
}
struct node{
bool f;int num,l,r,left,right;
}tree[N<<2];
int cnt=0;
void build(int &x,int l,int r){
x=++cnt;tree[x].l=l;tree[x].r=r;tree[x].f=true;
if (l==r){
tree[x].num=tree[x].left=tree[x].right=0;
return ;
}
int mid=(l+r)>>1;
build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);
}
inline void pushdown(int x){
int l1=tree[x].left,r1=tree[x].right;
// tree[l1].f=tree[r1].f=false;
tree[l1].f^=1;tree[r1].f^=1;
tree[l1].num=tree[l1].r-tree[l1].l+1-tree[l1].num;
tree[r1].num=tree[r1].r-tree[r1].l+1-tree[r1].num;
tree[x].f=true;
}
inline int query(int x,int l,int r){
if (l<=tree[x].l&&r>=tree[x].r)return tree[x].num;
if (tree[x].f==false) pushdown(x);
int mid=(tree[x].l+tree[x].r)>>1;
int ans1=0,ans2=0;
if (l<=mid) ans1=query(tree[x].left,l,r);
if (r>mid) ans2=query(tree[x].right,l,r);
return ans1+ans2;
}
inline void updata(int x){
tree[x].num=tree[tree[x].left].num+tree[tree[x].right].num;
}
inline void change(int x,int l,int r){
if (l<=tree[x].l&&r>=tree[x].r){
tree[x].f^=1;
tree[x].num=tree[x].r-tree[x].l+1-tree[x].num;
return;
}
if (tree[x].f==false) pushdown(x);
int mid=(tree[x].l+tree[x].r)>>1;
if (l<=mid) change(tree[x].left,l,r);
if (r>mid) change(tree[x].right,l,r);
updata(x);
}
int n,m,root,op,a,b;
void print(int x){
if (tree[x].left) print(tree[x].left);
printf("%d %d\n",tree[x].l,tree[x].r);
if (tree[x].right) print(tree[x].right);
}
int main(){
//freopen("3870.in","r",stdin);
// freopen("3870.out","w",stdout);
n=read();m=read();build(root,1,n);
// print(root);
for (int i=1;i<=m;++i){
op=read();a=read();b=read();
if (op) printf("%d\n",query(root,a,b));
else change(root,a,b);
// printf("%d\n",tree[root].num);
}
return 0;
}