学步园

第一个线段树，大部分时间都在寒假挥霍了。最近迫切需要女朋友，又没有现成的，又不会找，恰似M67所言：“欲火焚身”那

#include<iostream><br /> using namespace std;<br /> const int sup=8010;<br /> int ans[sup];<br /> struct node<br /> {<br /> int left,right;<br /> int color;<br /> node *rch,*lch;<br /> node(int beg,int end)<br /> {<br /> left=beg;<br /> right=end;<br /> rch=NULL;<br /> lch=NULL;<br /> color=-1;//新建节点的区间段初始没有颜色标记<br /> }<br /> };<br /> node* creat_tree(int beg,int end)<br /> {<br /> node* tmp=new node(beg,end);<br /> if(end-beg>1)<br /> {<br /> tmp->lch=creat_tree(beg,(beg&end)+((beg^end)>>1));<br /> tmp->rch=creat_tree((beg&end)+((beg^end)>>1),end);<br /> }<br /> return tmp;<br /> }<br /> void insert(node* root,int L,int R,int c)<br /> {<br /> if(L==root->left && R==root->right || c==root->color)//区间重复或者涂色重复<br /> {<br /> root->color=c;<br /> return;<br /> }<br /> if(root->color>=0)//单色，那么子区间也是单色，但由于涂上的新色c不与root区间上任意色重复，故root大区间变成多色，而子区间暂时均为单色<br /> {<br /> root->lch->color=root->color;<br /> root->rch->color=root->color;<br /> }<br /> root->color=-2;//变为多色<br /> int mid=(root->left&root->right)+((root->left^root->right)>>1);<br /> if(R<=mid)<br /> insert(root->lch,L,R,c);<br /> else if(L>=mid)<br /> insert(root->rch,L,R,c);<br /> else<br /> {<br /> insert(root->lch,L,mid,c);<br /> insert(root->rch,mid,R,c);<br /> }<br /> }<br /> void count(node* root,int &c)//计算root区间上颜色c所占的线段数<br /> {<br /> if(root->color>=0 && c!=root->color)//单色且root上没有c这种颜色，那么更新c<br /> {<br /> c=root->color;<br /> ++ans[c];//新色新增一个线段<br /> }<br /> else if(-2==root->color)//当前大区间段包含多余一种颜色,那么就要细分，去找只包含一种颜色的子线段<br /> {<br /> count(root->lch,c);<br /> count(root->rch,c);<br /> }<br /> else<br /> c=root->color;//当前区间段还未上色，那么c初始化为空白<br /> }<br /> int main()<br /> {<br /> int n,i;<br /> int a,b,c;<br /> node* root;<br /> while(EOF!=scanf("%d",&n))<br /> {<br /> root=creat_tree(0,sup);//初始建立线段树<br /> while(n--)<br /> {<br /> scanf("%d%d%d",&a,&b,&c);<br /> insert(root,a,b,c);<br /> }<br /> fill(ans,ans+sup,0);<br /> int colo=-1;//初始空白<br /> count(root,colo);<br /> for(i=0;i<sup;++i)<br /> if(ans[i])<br /> printf("%d %d/n",i,ans[i]);<br /> printf("/n");<br /> }<br /> return 0;<br /> }