題目鏈接：http://poj.org/problem?id=2528 線段樹比較基礎(chǔ)的題目，比較捉急的就是離散化，離散化就是將大的區(qū)間映射到小的區(qū)間中，具體的看代碼吧，這個(gè)是傻崽大神的代碼，本菜的話決計(jì)寫不出來這么巧妙的代碼，不過不得不說，這次受益匪淺，以后我想我會(huì)記住這些東西……
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 11111;
11 bool hash[maxn];
12 int li[maxn], ri[maxn];
13 int X[maxn * 3];
14 int col[maxn << 4];
15 int cnt;
16 void PushDown(int rt){
17 if (col[rt] != -1){
18 col[rt << 1] = col[rt << 1 | 1] = col[rt];
19 col[rt] = -1;
20 }
21 }
22 void update(int ll, int rr, int c, int l, int r, int rt){
23 if (ll <= l && rr >= r){
24 col[rt] = c;
25 return;
26 }
27 PushDown(rt);
28 int m = (l + r) >> 1;
29 if (ll <= m) update(ll, rr, c, lson);
30 if (rr > m) update(ll, rr, c, rson);
31 }
32 void query(int l, int r, int rt){
33 if (col[rt] != -1){
34 if (!hash[col[rt]]) cnt += 1;
35 hash[col[rt]] = true;
36 return;
37 }
38 if (l == r) return;
39 int m = (l + r) >> 1;
40 query(lson);
41 query(rson);
42 }
43 int Bin(int key, int n, int X[]){
44 int l = 0, r = n - 1;
45 while (l <= r){
46 int m = (l + r) >> 1;
47 if (X[m] == key) return m;
48 if (X[m] < key) l = m + 1;
49 else r = m - 1;
50 }
51 }
52 int main(){
53 int t;
54 scanf("%d", &t);
55 while (t--){
56 int n; scanf("%d", &n);
57 int nn = 0;
58 for (int i = 0; i < n; i++){
59 scanf("%d%d", &li[i], &ri[i]);
60 X[nn++] = li[i];
61 X[nn++] = ri[i];
62 }
63 sort(X, X + nn);
64 int m = 1;
65 for (int i = 1; i < nn; i++){
66 if (X[i] != X[i - 1]) X[m++] = X[i];
67 }
68 sort(X, X + m);
69 for (int i = m - 1; i > 0; i--){
70 if (X[i] != X[i - 1] + 1) X[m++] = X[i - 1] + 1;
71 }
72 sort(X, X + m);
73 memset(col, -1, sizeof(col));
74 for (int i = 0; i < n; i++){
75 int l = Bin(li[i], m, X);
76 int r = Bin(ri[i], m, X);
77 update(l, r, i, 0, m, 1);
78 }
79 cnt = 0;
80 memset(hash, 0, sizeof(hash));
81 query(0, m, 1);
82 printf("%d\n", cnt);
83 }
84 return 0;
85
|