【题解】Luogu P3870 【[TJOI2009]开关】

这道题明显是一道线段树版题。

不过,它的lazy标签与一般的线段树有一定区别:普通线段树记录的是整体加减,而这里记录的是整体的进行取反操作的次数。

即区间内的所有1变0,0变1。

我们很容易的得知,两次(偶数次)取反操作对于区间没有影响,因此我们的lazy只需要记录操作次数的奇偶,因而我们可以用bool函数vis记录奇偶(当做lazy标签),每次区间整体操作时只需对vis进行成对变换(取反亦可),而该节点的真实值变为r-l-val(原值)+1,即区间原来关着的灯。

那么,pushdown时,若根节点的vis为真,就将两个子节点vis均取反,值变为r-l-val+1;若根节点的vis为零则不用做任何操作,所以我们可以对此优化——在pushdown前先判断vis,若为假则不用pushdown。

以下为代码。注意:vis数组大小为4 \times maxn

#include<cstdio>
#define lt	(root<<1)
#define rt	((root<<1))+1
#define maxn 100005
using namespace std;

struct tree{
	int l;
	int r;
	int open;
};
tree t[maxn<<2];
bool vis[maxn<<2];//lazy数组
int n,m;
inline int read()//快速读入,在此相当于scanf
{
	char c = getchar();int x = 0;
	while(c<'0'||c>'9')
		c = getchar();
	while(c>='0'&&c<='9')
	{
		x = x*10 + c-'0';
		c = getchar();
	}
	return x;
}

inline void pushdown(int root)//在使用pushdown前已有判断vis,故此不再判断
{
	t[lt].open = t[lt].r - t[lt].l-t[lt].open+1;
	t[rt].open = t[rt].r - t[rt].l-t[rt].open+1;
	vis[lt]^=1;vis[rt]^=1;vis[root] = 0;
}

void built(int l,int r,int root)//建树,因为默认值为0,所以不用给open(val)赋值
{
	t[root].l = l;t[root].r =r;
	if(l==r)	return;
	int mid = l+r >> 1;
	built(l,mid,lt);
	built(mid+1,r,rt);
}



void	change(int l,int r,int root)
{
	int nl = t[root].l , nr = t[root].r;
	if(nl==l&&nr==r){
		vis[root]^=1;
		t[root].open = t[root].r-t[root].l-t[root].open+1;
		return ;
	}
	else if(vis[root])	pushdown(root);//判断是否需要pushdown 
	int mid = nl+nr >> 1;
	if(r<=mid)	change(l,r,lt);
	else if(l>=mid+1)	change(l,r,rt);
	else{
		change(l,mid,lt);
		change(mid+1,r,rt);
	}
	t[root].open = t[lt].open + t[rt].open;
	return ;
}

int find(int l,int r,int root)
{
	int nl = t[root].l , nr = t[root].r;
	if(nl==l&&nr==r)
		return t[root].open;
	else if(vis[root])	pushdown(root);
	int mid = nl+nr >> 1;//判断两个区间的相对位置 
	if(r<=mid)	return find(l,r,lt);
	else if(l>=mid+1)	return find(l,r,rt);
	else	return find(l,mid,lt)+find(mid+1,r,rt);	
}
int main(){
	//freopen("123.in","r",stdin);
	n = read();m=read();
	built(1,n,1);
	int temp,l,r;
	for(int i=1;i<=m;i++)
	{
		temp = read();l=read();r=read();
		if(temp==0)		add(l,r,1); 
		else printf("%d\n",find(l,r,1));
	}
	return 0;
}