首页 > POJ解题报告 > POJ 2777 Count Color 线段树

POJ 2777 Count Color 线段树

最近,搞完这个,就复习其他数据结构。这个题想了好久,知道用线段树,却不知道怎么解题。最后看了数据结构书才搞出来。就是给节点设置一个cover域,cover为0代表线段存在多种颜色,非零,代表纯色,数值用于区别颜色种类。

第一次建树时,根节点cover域为1。以后要涂色的时候,先看涂色区域是否覆盖当前节点的范围,如果覆盖,直接更改当前节点的cover域。否则,先看当前节点是否为纯色,如果是纯色,就要把纯色信息传递给左右子树,而当前节点cover域则变为0.表明当前节点覆盖的颜色不在是纯色,这样照着这个思路递归更新子节点的cover域。查询就比较简单了,中间用一个数组来表示哪些颜色已经上色。感觉我说的不是很清楚,看源代码吧。我一直很欣赏自己的线段树代码……POJ2777

//Coded by 代码疯子
//http://www.programlife.net/
//POJ2777 SegMent Tree 线段树
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAXNUM 100010
#define CLRNUM 32

typedef struct TagNode
{
	int left;
	int right;
	int cover;
}Node;

Node node[3*MAXNUM];
bool clr[CLRNUM];

void TreeMake(int x, int y, int idx)
{
	node[idx].left = x;
	node[idx].right = y;
	
	if(x == y)
	{
		return ;
	}
	int mid = (node[idx].left + node[idx].right) >> 1;
	TreeMake(x, mid, idx<<1);
	TreeMake(mid + 1, y, (idx<<1)+1);
}

void TreeUpdate(int x, int y, int col, int idx)
{
	if(x <= node[idx].left && y >= node[idx].right)
	{
		node[idx].cover = col;
		return ;
	}
	else
	{
		if(node[idx].cover >= 1)	//纯色
		{
			node[idx<<1].cover = node[idx].cover;		//纯色
			node[(idx<<1)+1].cover = node[idx].cover;	//纯色
			node[idx].cover = 0;	//混合颜色
		}
		int mid = (node[idx].left + node[idx].right) >> 1;
		
		if(x > mid)
		{
			TreeUpdate(x, y, col, (idx<<1)+1);
		}
		else if(y <= mid)
		{
			TreeUpdate(x, y, col, idx << 1);
		}
		else
		{
			TreeUpdate(x, mid, col, idx<<1);
			TreeUpdate(mid + 1, y, col, (idx<<1)+1);
		}
	}
}

void TreeQuery(int x, int y, int idx)
{
	if(node[idx].cover > 0)
	{
		clr[node[idx].cover] = 1;
	}
	else
	{
		int mid = (node[idx].left + node[idx].right) >> 1;
		if(x > mid)
		{
			TreeQuery(x, y, (idx<<1)+1);
		}
		else if(y <= mid)
		{
			TreeQuery(x, y, idx<<1);
		}
		else
		{
			TreeQuery(x, mid, idx<<1);
			TreeQuery(mid + 1, y, (idx<<1)+1);
		}
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	
	int l, t, n, i, j;
	char ch;
	int a, b, c, sum;
	while(EOF != scanf("%d %d %d%*c", &l, &t, &n))
	{
		TreeMake(1, l, 1);
		node[1].cover = 1;
		for(i = 1; i <= n; ++i)
		{
			scanf("%c", &ch);
			if(ch == 'C')
			{
				scanf("%d %d %d%*c", &a, &b, &c);
				TreeUpdate(a, b, c, 1);
			}
			else 
			{
				scanf("%d %d%*c", &a, &b);
				memset(clr, 0, sizeof(clr));
				TreeQuery(a, b, 1);
				sum = 0;
				for(j = 1; j <= t; ++j)
				{
					if(clr[j])++sum;
				}
				printf("%d\n", sum);
			}
		}
	}

	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 2777 Count Color 线段树
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2010年10月27日11:12 | #1

    来回访一下

    [回复]

    代码疯子 回复:

    欢迎O(∩_∩)O~

    [回复]

  2. 2010年10月27日13:05 | #2

    来看看 最近天冷又开始懒了

    [回复]

    代码疯子 回复:

    估计大范围都降温了 O(∩_∩)O~

    [回复]

  3. 2010年10月27日15:13 | #3

    哈哈`我又来了

    [回复]

  4. momo
    2012年9月30日15:50 | #4

    如果顏色是交錯的,不就爆炸了嘛?

    [回复]

  1. 本文目前尚无任何 trackbacks 和 pingbacks.