题目链接:http://poj.org/problem?id=2528 线段树比较基础的题目,比较捉急的就是离散化,离散化就是将大的区间映射到小的区间中,具体的看代码吧,这个是傻崽大神的代码,本菜的话决计写不出来这么巧妙的代码,不过不得不说,这次受益匪浅,以后我想我会记住这些东西……
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|