ZOJ1610--Count the ColorsAnalysis: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==1) return;
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==-2) return;
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