URAL-1019 Line Painting----暴力或线段树

题目链接：

https://cn.vjudge.net/problem/URAL-1019

题目大意：

一个0~1e9的区间，初始都是白的，现进行N次操作，每次将一段区间图上一中颜色。最后问说连续最长的白色区间。

解题思路：

先离散化，之后可暴力，或者用线段树维护

离散化后，染色时候应注意从第二个点开始染色。

比如：1 2 3 4 5 6 7 8 9 10，现在染色7 - 9

那么只需要把8 9 染色即可，因为7-9是两段区间，用8表示7-8区间，9表示8-9区间。

这样表示不会出错。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 10000 + 10;
 5 struct node
 6 {
 7     int u, v;
 8     char s[3];
 9 }a[maxn];
10 int num[maxn], tot, color[maxn];
11 map<int, int>Map;
12 int main()
13 {
14     int n;
15     cin >> n;
16     num[tot++] = 0, num[tot++] = 1e9;
17     for(int i = 1; i <= n; i++)
18     {
19         scanf("%d%d%s", &a[i].u, &a[i].v, &a[i].s);
20         num[tot++] = a[i].u;
21         num[tot++] = a[i].v;
22     }
23     sort(num, num + tot);
24     tot = unique(num, num + tot) - num;
25     for(int i = 0; i < tot; i++)
26     {
27         Map[num[i]] = i;
28     }
29     for(int i = 1; i <= n; i++)
30     {
31         int tmp = 0;
32         if(a[i].s[0] == 'b')tmp = 1;
33         for(int j = Map[a[i].u] + 1; j <= Map[a[i].v]; j++)
34         {
35             color[j] = tmp;
36         }
37         //for(int i = 0; i < tot; i++)cout<<color[i]<<" ";
38         //cout<<endl;
39     }
40     int l, r, length = 0;
41     for(int i = 0; i < tot; i++)
42     {
43         if(color[i])continue;
44         int j = i;
45         while(color[j] == 0 && j < tot)j++;
46         if(length < num[j - 1] - num[i - 1])
47         {
48             l = num[i - 1];
49             r = num[j - 1];
50             length = r - l;
51         }
52     }
53     cout<<l<<" "<<r<<endl;
54     return 0;
55 }

下次写上线段树的代码：