840
技術社區[雲棲]
線段樹-區間延遲修改-zoj-1610
Count the Colors
Description
Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.
Your task is counting the segments of different colors you can see at last.
Input
The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
x1 x2 c
x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.
All the numbers are in the range [0, 8000], and they are all integers.
Input may contain several data set, process to the end of file.
Output
Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.
If some color can't be seen, you shouldn't print it.
Print a blank line after every dataset.
Sample Input
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1
Sample Output
1 1
2 1
3 1
1 1
0 2
1 1
大意：為線段上的子線段塗不同顏色的色塊，新塗的會覆蓋掉舊的。對應於塗色過程的輸入為每行三個整數 x1 x2 c ，代表線段中本次塗色的子線段的起點與終點。問到最後每種顏色各有多少塊。
分析：將整個線段分割成單位長度為1的子線段。以數組color[i]表示(i,i+1)區間上的色塊顏色（從0開始記）。每次塗色，都要修改一個區間，所以用線段樹來維護區間信息。
最後更新：2017-04-03 12:56:39