# 不过一笑

Well life is tough,make a good laugh

C++博客 :: 首页 :: 联系 :: 聚合  :: 管理

### 公告

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 雨过有声 阅读(880) 评论(1)  编辑 收藏 引用 所属分类: ACM-ICPC

### Feedback

# re: Problem--ZOJ1610 Count the Colors(Segment Tree） 2011-03-26 11:47 a player