BZOJ1230: [Usaco2008 Nov]lites 开关灯线段树

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1230

分析:

在每个节点打标记，打完标记要反转当前节点灯。这个点打上标记表示下面子节点灯还没有反转，然而这个点的灯是反转的。

所以每次要先标记下标记下放，然后开始更新此节点。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m;
bool visit[400010];
int sum[400010];

void change_mean(int x,int l,int r)
{
	sum[x]=r-l+1-sum[x];
	return ;
}

void pushdown(int x,int l,int r)
{
	if(visit[x])
	{
		visit[x]=false;
		int mid=(l+r)>>1;
		change_mean(x<<1,l,mid);
		change_mean(x<<1|1,mid+1,r);
		visit[x<<1]^=1;
		visit[x<<1|1]^=1;
	}
	return ;
}

void change_tree(int step,int l,int r,int xx,int yy)
{
	pushdown(step,l,r);
	if(xx<=l&&yy>=r)
	{
		visit[step]=true;
		change_mean(step,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	if(xx>=mid+1)
	{
		change_tree(step<<1|1,mid+1,r,xx,yy);
	}
	else if(yy<=mid)
	{
		change_tree(step<<1,l,mid,xx,yy);
	}
	else 
	{
		change_tree(step<<1,l,mid,xx,yy);
		change_tree(step<<1|1,mid+1,r,xx,yy);
	}
	sum[step]=sum[step<<1]+sum[step<<1|1];
	return ;
}

int puery_tree(int step,int l,int r,int xx,int yy)
{
	if(xx<=l&&yy>=r)
	{
		return sum[step];
	}
	pushdown(step,l,r);
	int mid=(l+r)>>1;
	if(xx>=mid+1)
	{
		return puery_tree(step<<1|1,mid+1,r,xx,yy);
	}
	else if(yy<=mid)
	{
		return puery_tree(step<<1,l,mid,xx,yy);
	}
	else 
	{
		return puery_tree(step<<1,l,mid,xx,yy)+puery_tree(step<<1|1,mid+1,r,xx,yy);
	}
}

int main()
{
	int type,x1,y1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&type,&x1,&y1);
		if(!type)
		{
			change_tree(1,1,n,x1,y1);
		}
		else
		{
			printf("%d\n",puery_tree(1,1,n,x1,y1));
		}
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m;

bool visit[400010];

int sum[400010];

void change_mean(int x,int l,int r)

{

sum[x]=r-l+1-sum[x];

return ;

}

void pushdown(int x,int l,int r)

{

if(visit[x])

{

visit[x]=false;

int mid=(l+r)>>1;

change_mean(x<<1,l,mid);

change_mean(x<<1|1,mid+1,r);

visit[x<<1]^=1;

visit[x<<1|1]^=1;

}

return ;

}

void change_tree(int step,int l,int r,int xx,int yy)

{

pushdown(step,l,r);

if(xx<=l&&yy>=r)

{

visit[step]=true;

change_mean(step,l,r);

return ;

}

int mid=(l+r)>>1;

if(xx>=mid+1)

{

change_tree(step<<1|1,mid+1,r,xx,yy);

}

else if(yy<=mid)

{

change_tree(step<<1,l,mid,xx,yy);

}

else

{

change_tree(step<<1,l,mid,xx,yy);

change_tree(step<<1|1,mid+1,r,xx,yy);

}

sum[step]=sum[step<<1]+sum[step<<1|1];

return ;

}

int puery_tree(int step,int l,int r,int xx,int yy)

{

if(xx<=l&&yy>=r)

{

return sum[step];

}

pushdown(step,l,r);

int mid=(l+r)>>1;

if(xx>=mid+1)

{

return puery_tree(step<<1|1,mid+1,r,xx,yy);

}

else if(yy<=mid)

{

return puery_tree(step<<1,l,mid,xx,yy);

}

else

{

return puery_tree(step<<1,l,mid,xx,yy)+puery_tree(step<<1|1,mid+1,r,xx,yy);

}

int main()

{

int type,x1,y1;

scanf("%d%d",&n,&m);

for(int i=1;i<=m;++i)

{

scanf("%d%d%d",&type,&x1,&y1);

if(!type)

{

change_tree(1,1,n,x1,y1);

}

else

{

printf("%d\n",puery_tree(1,1,n,x1,y1));

}

return 0;

}

没有回路的路