不过一笑

Well life is tough,make a good laugh

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 1 Comments :: 0 Trackbacks

公告

This guy's no expert,he's just to build a solid foundation,that may turn out to be useful in the future

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

ZOJ1610--Count the Colors
Analysis:
This is obviously a problem that we can solve using the data structure called Segment Tree.Specifically for this problem,we can build a Segment Tree according to the input datas.First,we get all datas from the input,and find out the longest segment modified.Then we build the tree with the longest segment as its root.After that,we can implement each manipulation one by one,using the Insert_Segment function.Note that every single modification should be carried out exactly from the root of the tree,due to the charateristics of the Segment Tree.Finally,we use a function Count_Color to calculate the number of segments on which each color is visible.Note that we should merge two joint segments into one when counting.This process is important and necessary only because we did not do such thing when 'painting' the segments,i.e,when a segment [a,b](a<b) is painted with a single color,we did not paint all its successive segments with the same color,which we could've done.However,for this problem solely,we really should not do that when painting,due to the fact that this problem requires only one 'query'.That being true,why not save the time and do that job only once?
Code(in C++):
  1 #include<iostream>
  2 #include<cstring>
  3 #define MAXSIZE 32000
  4 using namespace std;
  5 struct segment
  6 {
  7     int color;//color>=0 indicates that this segment is monochrome,while color==-1 indicates polychrome.A value -2 indicates the original state
  8     int start,end;//the starting and ending point of a segment
  9 }seg[MAXSIZE];
 10 struct Dye
 11 {
 12     int left,right,chrome;
 13 }manipulation[8000],visible[8000];
 14 void Build(int num,int left,int right)
 15 {
 16     seg[num].start=left;seg[num].end=right;seg[num].color=-2;//set the original state of the current segment
 17     if(left+1==right) return;//if the segment cannot be divided any more,return
 18     int mid=(left+right)/2;//divide it into two
 19     Build(num*2,left,mid);Build(num*2+1,mid,right);//Build the left and right child of the current segment,respectively
 20 }
 21 /*This function is used to build a segment tree,with its parameters representing the index of
 22 the root(num),the starting point of the total segment(left),and the ending point of the total
 23 segment(right),respectively*/
 24 void Insert_Segment(int num,int left,int right,int chrome)
 25 {
 26     if(seg[num].color!=chrome)
 27     {
 28         if(left==seg[num].start && right==seg[num].end)
 29         {
 30             seg[num].color=chrome;
 31             if(num==1return;
 32             if(num%2==0)
 33             {
 34                 if(seg[num+1].color==chrome) seg[num/2].color=chrome;
 35             }
 36             else if(seg[num-1].color==chrome) seg[num/2].color=chrome;
 37             return;
 38         }//if the color segment is exactly the current segment,then color it and return
 39         else if(seg[num].color>=0)
 40         {
 41             seg[2*num].color=seg[num].color;
 42             seg[2*num+1].color=seg[num].color;
 43         }//if the color segment does not match the current segment perfectly,and the current segment was monochrome
 44          //then paint its children its original color,and move on
 45         seg[num].color=-1;//two scenarios will lead us here:the segment has its original color
 46                           //and gets mixed by the current painting,or the segment was a polychrome
 47                           //one.Either way,we should mark it as polychrome here and move on
 48         int mid=(seg[num].start+seg[num].end)/2;//find the middle point of the segment,looking to paint it
 49         if(mid>=right)
 50         {
 51             Insert_Segment(2*num,left,right,chrome);
 52             if(seg[2*num].color==seg[2*num+1].color && seg[2*num].color>=0)
 53                 seg[num].color=seg[2*num].color;
 54         }
 55         else if(mid<=left)
 56         {
 57             Insert_Segment(2*num+1,left,right,chrome);
 58             if(seg[2*num].color==seg[2*num+1].color && seg[2*num].color>=0)
 59                 seg[num].color=seg[2*num].color;
 60         }
 61         else
 62         {
 63             Insert_Segment(2*num,left,mid,chrome);
 64             Insert_Segment(2*num+1,mid,right,chrome);
 65             if(seg[2*num].color==seg[2*num+1].color && seg[2*num].color>=0)
 66                 seg[num].color=seg[2*num].color;//if the two child segments end up with the same
 67                                                 //monochrome,update the father segment
 68         }//decide in which area should the paint be carried on
 69     }//all the above should only be done when the chrome to be painted is not the same as the
 70      //original color of the current segment
 71 }
 72 /*This function is used to insert paint area into the segment tree we have built,with its parameters
 73 representing the index of the root of the tree(num),the starting and ending point of the paint
 74 segment(left,right),as well as the color of the paint(chrome),respectively*/
 75 void Count_Color(int num,int left,int right)
 76 {
 77     if(left+1==right && seg[num].color==-2return;
 78     if(seg[num].color>=0)
 79     {
 80         //printf("%d %d %d\n",seg[num].start,seg[num].end,seg[num].color);
 81         if(seg[num].start==visible[seg[num].color].right)
 82             visible[seg[num].color].right=seg[num].end;
 83         else if(seg[num].end==visible[seg[num].color].left)
 84             visible[seg[num].color].left=seg[num].start;
 85         else
 86         {
 87             visible[seg[num].color].chrome++;
 88             visible[seg[num].color].left=seg[num].start;
 89             visible[seg[num].color].right=seg[num].end;
 90         }
 91         return;
 92     }//if the current segment if monochrome,then the color of it is visible,obviously.In addition,
 93      //all the segments who are the children of it stays invisible.Consequencely,the counting
 94      //process should be ended.
 95     else
 96     {
 97         int mid=(left+right)/2;
 98         Count_Color(num*2,left,mid);
 99         Count_Color(num*2+1,mid,right);
100     }
101     //Either the current segment is polychrome,or remaining untouched,the counting should process
102     //down to its children.
103 }
104 /*This function is used to decide on the visibility together with the number of segments of each
105 color,with its parameters representing the index of the root of the tree(num),the startpoint and
106 the endpoint of the total segment(left,right),respectively.*/
107 void Output(int left,int right)
108 {
109     for(int i=left;i<=right;i++)
110     {
111         if(visible[i].chrome)
112         {
113             printf("%d %d\n",i,visible[i].chrome);
114         }
115     }
116     printf("\n");
117 }
118 int main()
119 {
120     int n,mleft,mright,lcolor,rcolor;
121     while(scanf("%d",&n)==1)
122     {
123         mleft=lcolor=8001;mright=rcolor=0;
124         for(int i=0;i<n;i++)
125         {
126             scanf("%d %d %d",&manipulation[i].left,&manipulation[i].right,&manipulation[i].chrome);
127             if(mleft>manipulation[i].left) mleft=manipulation[i].left;
128             if(mright<manipulation[i].right) mright=manipulation[i].right;
129             if(lcolor>manipulation[i].chrome) lcolor=manipulation[i].chrome;
130             if(rcolor<manipulation[i].chrome) rcolor=manipulation[i].chrome;
131         }//Input all the manipulations,and find out the leftmost and rightmost endpoint of the area
132          //together with the lowest and highest index of the color used
133         Build(1,mleft,mright);//Build the segment tree due to the largest segment area
134         for(int i=0;i<n;i++)
135         {
136             Insert_Segment(1,manipulation[i].left,manipulation[i].right,manipulation[i].chrome);
137         }//Implement the manipulations
138         for(int i=lcolor;i<=rcolor;i++)
139         {
140             visible[i].chrome=0;
141             visible[i].left=visible[i].right=-1;
142         }
143         Count_Color(1,mleft,mright);//Count the colors visible
144         Output(lcolor,rcolor);//Output the results
145     }
146     return 0;
147 }
148 

posted on 2010-08-12 00:56 雨过有声 阅读(944) 评论(1)  编辑 收藏 引用 所属分类: ACM-ICPC

Feedback

# re: Problem--ZOJ1610 Count the Colors(Segment Tree) 2011-03-26 11:47 a player
其实,线段树在英语里是Interval Tree而不是Segment Tree..  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理