P3870 [TJOI2009] 开关

题目描述

现有 nn 盏灯排成一排，从左到右依次编号为：11，22，……，nn。然后依次执行 mm 项操作。

操作分为两种：

1. 指定一个区间 [a,b][a,b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
2. 指定一个区间 [a,b][a,b]，要求你输出这个区间内有多少盏灯是打开的。

灯在初始时都是关着的。

输入格式

第一行有两个整数 nn 和 mm，分别表示灯的数目和操作的数目。

接下来有 mm 行，每行有三个整数，依次为：cc、aa、bb。其中 cc 表示操作的种类。

• 当 cc 的值为 00 时，表示是第一种操作。
• 当 cc 的值为 11 时，表示是第二种操作。

aa 和 bb 则分别表示了操作区间的左右边界。

输出格式

每当遇到第二种操作时，输出一行，包含一个整数，表示此时在查询的区间中打开的灯的数目。

样例输入：

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

输出

1
2

父节点下放到子节点，当父节点没有懒标记时，直接return，出现懒标记时，说明子节点数据要更新了，对于开灯关灯，一个区间对于已经开灯的数量，再次操作后就是这个区间长-当前开灯数量就是再次开灯时的数量。例如（1,0,1,0）区间1-4两个灯开着，再次启动1-4按钮时，开灯数量就是4-当前开灯的数量（2）。然后把子节点懒标记取反。

void pushdown(int idx,int l,int r)
{
    //当前没有懒标记
	if(laz[idx]^1) return ;
	
	laz[idx<<1]^=1;
	laz[idx<<1|1]^=1; 
	int mid=(l+r)>>1;
	tre[idx<<1]=(mid-l+1)-tre[idx<<1];
	tre[idx<<1|1]=(r-mid)-tre[idx<<1|1];
	laz[idx]^=1;
}

update操作，若区间(l,r)∈（x，y）父节点直接懒标记，更新后的开灯数量=区间长-上一次开灯的数量，这一道题最重要的就是这一点tre[idx]=(r-l+1)-tre[idx];

void update(int idx,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		laz[idx]^=1;
		tre[idx]=(r-l+1)-tre[idx];
		return ;
	}
	pushdown(idx,l,r);
	int mid=(r+l)>>1;
	if(x<=mid) update(idx<<1,l,mid,x,y);
	if(mid<y) update(idx<<1|1,mid+1,r,x,y);
	
	tre[idx]=tre[idx<<1]+tre[idx<<1|1];
}

query直接写板子即可。

完整代码（注意若不是用结构体，数组的大小要最少开到4*N）

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int tre[N],laz[N],n,m; 
void build(int idx,int l,int r)
{
	if(l==r)
	{
		tre[idx]=0;
		laz[idx]=0;
		return ;
	}
	tre[idx]=tre[idx<<1]+tre[idx<<1|1];
}
void pushdown(int idx,int l,int r)
{
	if(laz[idx]^1) return ;
	
	laz[idx<<1]^=1;
	laz[idx<<1|1]^=1; 
	int mid=(l+r)>>1;
	tre[idx<<1]=(mid-l+1)-tre[idx<<1];
	tre[idx<<1|1]=(r-mid)-tre[idx<<1|1];
	laz[idx]^=1;
}
void update(int idx,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		laz[idx]^=1;
		tre[idx]=(r-l+1)-tre[idx];
		return ;
	}
	pushdown(idx,l,r);
	int mid=(r+l)>>1;
	if(x<=mid) update(idx<<1,l,mid,x,y);
	if(mid<y) update(idx<<1|1,mid+1,r,x,y);
	
	tre[idx]=tre[idx<<1]+tre[idx<<1|1];
}
int query(int idx,int l,int r,int x,int y)
{
	if(l>=x&&r<=y) 
	{
		return tre[idx];
	}
	
	pushdown(idx,l,r);
	int mid=(l+r)>>1,ans=0;
	if(x<=mid) ans+=query(idx<<1,l,mid,x,y);
	if(mid<y) ans+=query(idx<<1|1,mid+1,r,x,y);
	return ans;
}
int main()
{
   ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
   cin>>n>>m;
   build(1,1,n);
   while(m--)
   {
   	  int op,x,y;
   	  cin>>op>>x>>y;
   	  if(op==0) update(1,1,n,x,y);
   	  else cout<<query(1,1,n,x,y)<<endl;
   }
  return 0;
}