线段树---zoj_1610

?????????线段树是一种二叉树的拓展，在线段树每个节点中，存储的是一个区间范围。对于每个节点，它的数据结构一般有，left,right,*lch,*rch，分别描述的是区间的左端点，区间的右端点，指向左子树的指针，指向右子树的指针。对于一个节点的左子树，它的区间范围是[left,(left+right)/2],对于一个节点的右子树，它的区间范围是[(left+right)/2,right]。

???????? 利用线段树可以解决很多问题，染色问题就是其中一类，zoj_1610

????????

#include<iostream>#include<cstdio>#include<string.h>using namespace std;int res[8010];int nc;int n,s,e,c;class node{public:int left,right;node* lch;node* rch;int color;//>=0 singal -1:uncolored -2:muti-colorednode(int start,int end){this->left=start;this->right=end;this->lch=NULL;this->rch=NULL;this->color=-1;}void creatTree(node*root){int end=root->right;int start=root->left;if(end-start>1){node* lt=new node(start,(start+end)/2);node* rt=new node((start+end)/2,end);root->lch=lt;root->rch=rt;creatTree(lt);creatTree(rt);}}void insert(node*root,int start,int end,int color){if((start==root->left&&end==root->right)||color==root->color){root->color=color;return;}if(root->color>=0){root->lch->color=root->color;root->rch->color=root->color;}root->color=-2;int mid=(root->left+root->right)/2;if(end<=mid){insert(root->lch,start,end,color);}else if(start>=mid){insert(root->rch,start,end,color);}else{insert(root->lch,start,mid,color);insert(root->rch,mid,end,color);}}void count(node*root){if(root->color>=0&&nc!=root->color){nc=root->color;++res[nc];}else if(root->color==-2){count(root->lch);count(root->rch);}else{nc=root->color;}}};node* createTree(int start,int end){node* tmp=new node(start,end);if(end-start>1){tmp->lch=createTree(start,(start+end)/2);tmp->rch=createTree((start+end)/2,end);}return tmp;}/*int average(int a,int b){int r=(a&b)+((a^b)>>1);cout<<r<<endl;}*/int main(){freopen("e:\\zoj\\zoj_1610.txt","r",stdin);while(cin>>n){//node* tree=createTree(0,8010);node*tree=new node(0,8010);tree->creatTree(tree);memset(res,0,sizeof(res));nc=-1;while(n--){scanf("%d%d%d",&s,&e,&c);tree->insert(tree,s,e,c);}tree->count(tree);for(int i=0;i<8010;i++)if(res[i])printf("%d %d\n",i,res[i]);printf("\n");}return 0;}

?