静态:
#include<iostream>
using namespace std;
#define N 16010
#define M 10000
#define Noc -1
#define Muc -2
struct Node{
int a,b,cover;
int lc,rc;
};
int color[M];
Node Tree[N];
int Len;
void build(int left,int right){
Len++; //增加一个新节点
int Now=Len;
Tree[Now].a=left; Tree[Now].b=right;
Tree[Now].cover=Noc;
Tree[Now].lc=-1;
Tree[Now].rc=-1;
if(right-left>1){ //非叶子节点，递归左右孩子
int mid=(left+right)>>1;
Tree[Now].lc=Len+1;
build(left,mid);
Tree[Now].rc=Len+1;
build(mid,right);
}
}
void insert(int root,int left,int right,int col){
if(left<=Tree[root].a&&right>=Tree[root].b||Tree[root].cover==col){
//当这个区间包函这个节点，或这个节点的颜色相同时直接涂抹颜色即可
Tree[root].cover=col;
return;
}
int lc1=Tree[root].lc,rc1=Tree[root].rc;
if(Tree[root].cover>=0){ //将父亲节点的值传递给孩子节点
Tree[lc1].cover=Tree[root].cover;
Tree[rc1].cover=Tree[root].cover;
}
Tree[root].cover=Muc; //此节点标记为混合颜色
int mid=(Tree[root].a+Tree[root].b)>>1;
if(right<=mid) insert(lc1,left,right,col); //当区间在左边时
else if(left>=mid) insert(rc1,left,right,col); //当区间在右边时
else{ //当区间在这个节点之间时
insert(lc1,left,mid,col);
insert(rc1,mid,right,col);
}
}
void getcount(int root,int& col){
if(Tree[root].cover>=0&&Tree[root].cover!=col){ //这个区间有被涂颜色，且这个区间和与之相连的区间颜色不同
col=Tree[root].cover;//将这个区间的颜色记录下来，防止与之相连的区间的颜色和它相同时被计算了值
color[col]++;
}
else if(Tree[root].cover==Muc){ //这个区间为混合颜色，递归左右节点
getcount(Tree[root].lc,col);
getcount(Tree[root].rc,col);
}
else col=Tree[root].cover; //将这个区间的颜色记录下来，防止与之相连的区间的颜色和它相同时被计算了值
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
Len=0;
build(0,8000); //建树
int a,b,c;
for(int i=0;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
insert(1,a,b,c); //插入，刷新值
}
memset(color,0,sizeof(color));
int col=Noc;
getcount(1,col); //统计正棵树的区间颜色
for(int i=0;i<M;++i)
if(color[i])
printf("%d %d\n",i,color[i]);
printf("\n");
}
return 0;
}
链表:
#include<iostream>
using namespace std;
#define Noc -1
#define Muc -2
#define N 8001
#define M 10000
struct Node{
int a,b,cover;
Node* lc;
Node* rc;
};
int colour[M];
Node* build(Node* Tree,int left,int right){
Node* now=new Node;
now->a=left;
now->b=right;
now->cover=Noc;
now->lc=NULL;
now->rc=NULL;
if(right-left>1){
int mid=(left+right)>>1;
now->lc=build(now->lc,left,mid);
now->rc=build(now->rc,mid,right);
}
return now;
}
void insert(Node* Tree,int left,int right,int col){
if(left<=Tree->a&&right>=Tree->b||Tree->cover==col){
Tree->cover=col;
return;
}
if(Tree->cover>=0){
Tree->lc->cover=Tree->cover;
Tree->rc->cover=Tree->cover;
}
Tree->cover=Muc;
int mid=(Tree->a+Tree->b)>>1;
if(right<=mid) insert(Tree->lc,left,right,col);
else if(left>=mid) insert(Tree->rc,left,right,col);
else{
insert(Tree->lc,left,mid,col);
insert(Tree->rc,mid,right,col);
}
}
void getcount(Node* Tree,int& col){
if(Tree->cover>=0&&Tree->cover!=col){
col=Tree->cover;
colour[col]++;
}
else if(Tree->cover==Muc){
getcount(Tree->lc,col);
getcount(Tree->rc,col);
}
else col=Tree->cover;
}
int main()
{
Node* root;
int n;
while(scanf("%d",&n)!=EOF){
root=build(root,0,N);
int a,b,c;
for(int i=0;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
insert(root,a,b,c);
}
memset(colour,0,sizeof(colour));
int col=Noc;
getcount(root,col);
for(int i=0;i<M;++i)
if(colour[i])
printf("%d %d\n",i,colour[i]);
printf("\n");
}
return 0;
}
posted on 2009-04-22 20:04
xfstart07 阅读(107)
评论(0) 编辑 收藏 引用 所属分类:
代码库