Zoj 1610 Count the Colors(세그먼트 트리 + 구간 업데이트 + 폭력 계수)

제목 대의:
n번의 조작이 있는데 매번 한 선의 한 구간을 염색한다(색깔이 같지 않다). 때로는 뒤의 색깔이 앞의 색깔을 덮을 수도 있다. 마지막에 색을 칠하면 보이는 색깔이 몇 가지가 있고 색깔마다 몇 부분이 있느냐고 묻는다.
문제 해결 방법:
이 제목은 나무를 세울 때 약간 다르다. 점을 대상으로 하는 것이 아니라 구간을 대상으로 하는 것이다. 분명히 구간 나무의 구간을 조작하고 갱신할 때 구간을 단위로 해야 한다. 그리고 각 구간이 몇 번 나타날 때 구간 나무의 건수 특징에 따라 나무를 두루 훑어보고 해답을 구할 수 있다.

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 8005;
 7 struct node
 8 {
 9     int l, r, c;
10     int Mid()
11     {
12         return (r + l) / 2;
13     }
14 };
15 node tree[maxn*4];
16 int cnt[maxn], temp;
17 
18 void Build (int root, int l, int r)
19 {
20     tree[root].l = l;
21     tree[root].r = r;
22     tree[root].c = -1;
23     if (l == r - 1)
24         return ;
25     Build (2*root+1, l, tree[root].Mid());
26     Build (2*root+2, tree[root].Mid(), r);
27 }
28 void update (int root, int l, int r, int c)
29 {// ，
30     if (l==tree[root].l && tree[root].r==r)
31     {
32         tree[root].c = c;
33         return ;
34     }
35     if (tree[root].c != -1)
36     {
37         tree[2*root+1].c = tree[2*root+2].c = tree[root].c;
38         tree[root].c = -1;
39     }
40     if (l >= tree[root].Mid())
41         update (2*root+2, l, r, c);
42     else if (r <= tree[root].Mid())
43         update (2*root+1, l, r, c);
44     else
45     {
46         update (2*root+1, l, tree[root].Mid(), c);
47         update (2*root+2, tree[root].Mid(), r, c);
48     }
49 }
50 void Count (int root)
51 {
52     if (tree[root].c != -1)
53     {// 
54         if (tree[root].c != temp)// 
55             cnt[tree[root].c] ++;
56         temp = tree[root].c;
57         return ;
58     }
59     if (tree[root].l == tree[root].r-1)
60     {// ， 
61         temp = -1;
62         return ;
63     }
64     Count (2*root+1);
65     Count (2*root+2);
66 }
67 
68 int main ()
69 {
70     int n, m;
71     while (scanf ("%d", &n) != EOF)
72     {
73         Build (0, 0, maxn);
74 
75         while (n --)
76         {
77             int x, y, c;
78             scanf ("%d %d %d", &x, &y, &c);
79             update (0, x, y, c);
80         }
81         temp = -1;
82         memset (cnt, 0, sizeof(cnt));
83         Count(0);
84         for (int i=0; i<maxn; i++)
85             if (cnt[i])
86                 printf ("%d %d
", i, cnt[i]);
87         printf ("
");
88     }
89     return 0;
90 }