现有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）。
每当遇到第二种操作时，输出一行，包含一个整数：此时在查询的区间中打开的灯的数目。
4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4
1 2
线段树裸题
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int maxn = 100000 + 10 ; struct Node{ int l,r,lazy,sum; }p[maxn * 4]; int n,m; void Build_tree(int pos,int l,int r){ p[pos].l=l,p[pos].r=r; if(l==r) p[pos].sum=0; else{ int mid=(l+r)>>1; Build_tree(pos*2,l,mid); Build_tree(pos*2+1,mid+1,r); } } void add(int pos,int l,int r){ p[pos].lazy=~p[pos].lazy; p[pos].sum=(r-l+1)-p[pos].sum; } void update(int pos,int l,int r,int mid){ if(!p[pos].lazy) return ; add(pos*2,l,mid); add(pos*2+1,mid+1,r); p[pos].lazy=0; } void modify(int pos,int l,int r,int x,int y){ if(l>=x && r<=y) { p[pos].sum=(r-l+1)-p[pos].sum,p[pos].lazy=~p[pos].lazy; return ; } int mid=(l+r)>>1; update(pos,l,r,mid); if(x<=mid) modify(pos*2,l,mid,x,y); if(y>mid) modify(pos*2+1,mid+1,r,x,y); p[pos].sum=p[pos*2].sum+p[pos*2+1].sum; } int query(int pos,int l,int r,int x,int y){ if(l>=x && r<=y) return p[pos].sum; int mid=(l+r)>>1; update(pos,l,r,mid); int ans(0); if(x<=mid) ans+=query(pos*2,l,mid,x,y); if(y>mid) ans+=query(pos*2+1,mid+1,r,x,y); return ans; } int main() { cin>>n>>m; Build_tree(1,1,n); for(int i=1,c,a,b;i<=m;i++){ scanf("%d%d%d",&c,&a,&b); if(!c) modify(1,1,n,a,b); else printf("%d\n",query(1,1,n,a,b)); } return 0; }
原文：https://www.cnblogs.com/hfang/p/11837959.html