zoj 1610 线段树的颜色覆盖.txt

ACM资料大集合

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

//ZOJ 1610 线段树的颜色覆盖 
#define NMAX 8200

typedef struct dian
{
	int left;
	int right;
	int color;//初始color为-1,若颜色混合，为-10
}dian;

dian tree[NMAX*4];
int ccount[NMAX];
int has[NMAX];
int qujian[NMAX];
int sss;

void create_tree(int p,int l,int r)
{
	tree[p].left=l;tree[p].right=r;tree[p].color=-1;
	if(l+1==r) return;
	create_tree(2*p,l,(l+r)/2);
	create_tree(2*p+1,(l+r)/2,r);
}

void insert_tree(int p,int l,int r,int c)
{
	int mid=(tree[p].left+tree[p].right)/2;
	if(tree[p].left==l&&tree[p].right==r) tree[p].color=c;
	else
	{
		if(tree[p].color>=-1&&tree[p].right-tree[p].left>1) 
		{
			tree[2*p].color=tree[p].color;
			tree[2*p+1].color=tree[p].color;
			tree[p].color=-10;
		}
		if(r<=mid) insert_tree(2*p,l,r,c);
		else if(l>=mid) insert_tree(2*p+1,l,r,c);
		else
		{
			insert_tree(2*p,l,mid,c);
			insert_tree(2*p+1,mid,r,c);
		}
	}
}
/*
void count_solve2(int p)
{	//一次编列树，把找到的颜色（不管同一颜色想不想接）按次序放到一个数组里
	if(tree[p].color>=-1) 
	{
		qujian[++sss]=tree[p].color;
//		qujian[++sss]=tree[p].right;
	}
	else if(tree[p].color==-10)
	{
		count(2*p);
		count(2*p+1);
	}
}
*/
void print()
{
	int i;
	for(i=1;i<=sss;i++) printf("%d ",qujian[i]);
	cout<<endl;
}
/*
void solve2()
{	//方法2
	//一次编列树，把找到的颜色（不管同一颜色想不想接）按次序放到一个数组里
	//统计时编列数组，跳过数组中相邻的相同颜色计数
	int i;
	count(1);
//	print();
	i=1;
	while(qujian[i]==-1) i++;
	ccount[qujian[i]]=1;
	i++;
	for(;i<=sss;i++)
	{	//跳过相邻的相同颜色
		if(qujian[i-1]!=qujian[i]&&qujian[i]!=-1) ccount[qujian[i]]++;
	}
	for(i=0;i<=NMAX;i++)
	{
		if(ccount[i]>0) printf("%d %d\n",i,ccount[i]);
	}
	printf("\n");
}
*/
void count_solve1(int p,int &lc,int &rc)
{//统计颜色的段数
	int lmc,rmc;
	if(tree[p].color>=-1) 
	{	//被一种颜色覆盖
		if(tree[p].color>=0) ccount[tree[p].color]++;//找到一个颜色
		lc=tree[p].color;//上一层函数需要
		rc=tree[p].color;
	}
	else if(tree[p].color==-10)
	{	//多颜色覆盖
		if(tree[p].right-tree[p].left>1)
		{	//递归地求子节点颜色
			count_solve1(2*p,lc,lmc);
			count_solve1(2*p+1,rmc,rc);
			if(lmc==rmc&&lmc!=-1) ccount[lmc]--;//如果两颗子树相邻的两颜色相等			
		}
	}
}

void solve1()
{	//方法1
	//一次编列树，边编列边修正ccount[]
	int i,a,b;
	count_solve1(1,a,b);
	for(i=0;i<=NMAX;i++) 
	{
		if(has[i]==1&&ccount[i]>0)
		{
			printf("%d %d\n",i,ccount[i]);
		}
	}
	printf("\n");
}

int main()
{
	int i,num,la,ra,ca,tt;
	double fe,fs;
	while(scanf("%d",&num)!=EOF)
	{
		fs=clock();
		sss=0;
		memset(has,0,sizeof(has));
		memset(ccount,0,sizeof(ccount));
		create_tree(1,0,NMAX);
		for(i=1;i<=num;i++)
		{
			scanf("%d%d%d",&la,&ra,&ca);
			if(ra<la)
			{
				tt=la;
				la=ra;
				ra=tt;
			}
			if(la!=ra) insert_tree(1,la,ra,ca);
			has[ca]=1;
		}
		fe=clock();
		solve1();
		if(((double)(fe-fs))/CLOCKS_PER_SEC*1000>300) printf("no");
	}
	return 0;
}