poj(2777)——Count Color(lazy思想,成段更新,区间统计)
发布日期:2021-09-19 06:09:15 浏览次数:1 分类:技术文章

题目的意思是:

现在我们有l个数,然后标记为1到n,他们的单位长度都是1,然后在每个单位长度的地方我们只能染上一种颜色。

现在有两种操作:

 "C A B C"代表给A,B区间都染上C这种颜色。

 "P A B" 相当于是询问,需要输出A,B这个区间不同颜色的数量是多少。

一开始我在想要怎么求不同颜色的数量,后来发现题目中说颜色的范围是30种颜色,所以在这里我们就可以进行暴力枚举了。

这个染色问题我一开始没怎么懂,后来在纸上模拟了一下别人的代码,然后就理解了。

首先如果那个节点完全包含那个区间的话,那么我们就把这个节点标记上颜色,不往下更新了,这也是lazy思想,直到下次遇到且颜色与当前要标记的颜色不同时在往下更新。

询问的话,是从最上面开始找,如果发现有一个节点是纯色的话(也就是说它被标记过的话),那么就记录下来,并且可以直接返回了,因为纯色说明下面节点的颜色都与这个节点的颜色相同,因为它包含了下面的节点了。所以最后我们只需要遍历一遍颜色然后再计数就好了。

#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>using namespace std;#define maxn 111111struct node{	int l,r,col;}tree[maxn*4];bool cc[55];void build(int v,int l,int r){	tree[v].l=l;	tree[v].r=r;	tree[v].col=1;	if(l==r) return ;	int temp=v<<1;	int mid=(l+r)>>1;	build(temp,l,mid);	build(temp+1,mid+1,r);}void update(int v,int l,int r,int color){	if(tree[v].l==l&&tree[v].r==r){		tree[v].col=color;		return;	}	if(tree[v].col&&tree[v].col!=color){		int temp=v<<1;		tree[temp].col=tree[v].col;		tree[temp+1].col=tree[v].col;		tree[v].col=0;	}	int mid=(tree[v].l+tree[v].r)>>1;	int temp=v<<1;	if(r<=mid) update(temp,l,r,color);	else if(l>mid) update(temp+1,l,r,color);	else{		update(temp,l,mid,color);		update(temp+1,mid+1,r,color);	}}void query(int v,int l,int r){ 	if(tree[v].col>0){		cc[tree[v].col]=true;		return ;	}	int mid=(tree[v].l+tree[v].r)>>1;	int temp=v<<1;	if(r<=mid) query(temp,l,r);	else if(l>mid) query(temp+1,l,r);	else{		query(temp,l,mid);		query(temp+1,mid+1,r);	}}int main(){	int L,T,O;	char ss[4];	scanf("%d%d%d",&L,&T,&O);	build(1,1,L);	#if 1	while(O--){		scanf("%s",ss);		int a,b,c;		if(ss[0]=='C'){			scanf("%d%d%d",&a,&b,&c);			update(1,a,b,c);		}			else if(ss[0]=='P'){			int ans=0;			fill(cc,cc+55,false);			scanf("%d%d",&a,&b);			query(1,a,b);			for(int i=1;i<=T;i++){				if(cc[i]) ans++;			}			printf("%d\n",ans);		}	}	#endif}/*8 5 4C 5 6 1C 5 5 3C 6 6 4P 5 6*/

思路大致是这样的:

思路:

这个题与poj2528贴海报类似,涂色问题。之前做poj2528时并不知道这个思想,对代码理解的也不透彻。做了这道题以后,对Lazy-Tag思想有了更深的理解了。

 

当建立好一棵线段树之后,就是往上面涂色。涂色问题可分为以下几个步骤:

1.如果当前区间已经染色,且其颜色和欲染颜色相同,则直接退出(这句可以不要)

2.如果当前区间被欲染色区间完全覆盖,那么当前区间的子区间也被覆盖,那么直接给当前区间染上该颜色直接退出。

3.如果没有被完全覆盖,首先给左右子树染成当前区间的颜色,然后当前区间颜色赋值为混合色为0,再递归染色左右子树。

这样修改被完全覆盖的区间时就可以直接修改而不用遍历左右子树,而对于没有被完全覆盖的区间,先将其颜色传给左右子树,再递归修改,保证了子树颜色的正确性。大大降低了时间复杂度。

 

对于区间统计,设置mark数组,标记某一颜色是否显现出来。如果一个区间涂上了红色,那么这个区间的任何子区间都涂上了红色,mark标记为1,就不必向下遍历了。当是混合色(为0时)就要继续遍历子树。最后统计mark值为1的个数即可。

推荐一下这个人写的: http://www.2cto.com/kf/201402/277917.html
上一篇:poj(3667)——hotel(线段树区间合并)
下一篇:hdu(1698)——Just a Hook(成段更新,节点求和,lazy思想)

关于作者

    白红宇是个全栈工程师,前端vue,小程序,app开发到后端框架设计,数据库设计,环境部署上线运维。

最新文章