离散化其实就是把所有端点放在一起，然后排序去个重就好了。
比如说去重以后的端点个数为m，那这m个点就构成m-1个小区间。然后给这m-1个小区间编号1~m-1，再用线段树来做就行了。
具体思路是，从最后一张的海报来判断，如果海报覆盖的区域有空白区域那么这张海报就是可见的。并及时更新线段树信息。
说一个我调了很久的才发现小错误，比如书2 2这样一个海报，如果你把这张海报的左右端点都记作2的话那就是个空区间了。
其实，这张海报覆盖的是第2块瓷砖。所以R++，2 3就表示第2块瓷砖的左右端点。
当然，如果不是我这个思路，就可能不会出现这个问题。
这个是跟着去年北大的ACM培训班上给的标程写的，指针满天飞，个人感觉代码不够简洁。
1 //#define LOCAL 2 #include <iostream> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 7 int n; 8 struct CPost 9 { 10 int L, R; 11 }posters[10000 + 100]; 12 int x[20000 + 200]; //海报的端点瓷砖编号 13 int hash[10000000 + 10];//hash[i]表示瓷砖i所处的离散化后的区间编号 14 15 struct CNode 16 { 17 int L, R; 18 bool bCovered; //区间[L, R]是否已经完全覆盖 19 CNode *pLeft, *pRight; 20 }Tree[1000000]; 21 int nNodeCount = 0; 22 int Mid(CNode* pRoot) 23 { 24 return (pRoot->L + pRoot->R) / 2; 25 } 26 void BuildTree(CNode *pRoot, int L, int R) 27 { 28 pRoot->L = L; 29 pRoot->R = R; 30 pRoot->bCovered = false; 31 if(L == R) 32 return; 33 ++nNodeCount; 34 pRoot->pLeft = Tree + nNodeCount; 35 ++nNodeCount; 36 pRoot->pRight = Tree + nNodeCount; 37 BuildTree(pRoot->pLeft, L, (L+R)/2); 38 BuildTree(pRoot->pRight, (L+R)/2+1, R); 39 } 40 bool Post(CNode *pRoot, int L, int R) 41 {//插入一张覆盖区间[L, R]的海报，返回true则说明该区间是部分或者全部可见的 42 if(pRoot->bCovered) 43 return false; 44 if(pRoot->L == L && pRoot->R == R) 45 { 46 pRoot->bCovered = true; 47 return true; 48 } 49 bool bResult; 50 if(R <= Mid(pRoot)) 51 bResult = Post(pRoot->pLeft, L, R); 52 else if(L >= Mid(pRoot) + 1) 53 bResult = Post(pRoot->pRight, L, R); 54 else 55 { 56 bool b1 = Post(pRoot->pLeft, L, Mid(pRoot)); 57 bool b2 = Post(pRoot->pRight, Mid(pRoot) + 1, R); 58 bResult = b1 || b2; 59 } 60 //要更新的节点的覆盖情况 61 if(pRoot->pLeft->bCovered && pRoot->pRight->bCovered) 62 pRoot->bCovered = true; 63 return bResult; 64 } 65 66 int main(void) 67 { 68 #ifdef LOCAL 69 freopen("2528in.txt", "r", stdin); 70 #endif 71 int t; 72 int i, j, k; 73 scanf("%d", &t); 74 int nCaseNo = 0; 75 while(t--) 76 { 77 ++nCaseNo; 78 scanf("%d", &n); 79 int nCount = 0; 80 for(i = 0; i < n; ++i) 81 { 82 scanf("%d%d", &posters[i].L, &posters[i].R); 83 x[nCount++] = posters[i].L; 84 x[nCount++] = posters[i].R; 85 } 86 sort(x, x + nCount); 87 nCount = unique(x, x + nCount) - x;//元素去重 88 //将下面离散化 89 int nIntervalNo = 0; 90 for(i = 0; i < nCount; ++i) 91 { 92 hash[x[i]] = nIntervalNo; 93 if(i < nCount - 1) 94 { 95 if(x[i + 1] - x[i] == 1) 96 ++nIntervalNo; 97 else 98 nIntervalNo += 2; 99 } 100 } 101 102 BuildTree(Tree, 0, nIntervalNo); 103 int nSum = 0; 104 for(i = n - 1; i >= 0; --i) 105 {//从后往前遍历每个海报是否可见 106 if(Post(Tree, hash[posters[i].L], hash[posters[i].R])) 107 ++nSum; 108 } 109 printf("%d ", nSum); 110 } 111 return 0; 112 }
自己改成数组的写法，感觉可读性要好很多。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 100000 + 10; 7 int covered[maxn << 2]; 8 int n, m, L[maxn], R[maxn], x[maxn]; 9 10 bool post(int o, int L, int R, int qL, int qR) 11 { 12 if(covered[o]) return false; 13 if(qL == L && qR == R) { covered[o] = true; return true; } 14 int M = (L + R) / 2; 15 bool ok; 16 if(qR <= M) ok = post(o*2, L, M, qL, qR); 17 else if(qL > M) ok = post(o*2+1, M+1, R, qL, qR); 18 else 19 { 20 bool ok1 = post(o*2, L, M, qL, M); 21 bool ok2 = post(o*2+1, M+1, R, M+1, qR); 22 ok = ok1 || ok2; 23 } 24 if(covered[o*2] && covered[o*2+1]) covered[o] = true; 25 return ok; 26 } 27 28 int main() 29 { 30 //freopen("in.txt", "r", stdin); 31 32 int T; scanf("%d", &T); 33 while(T--) 34 { 35 scanf("%d", &n); 36 for(int i = 0; i < n; i++) 37 { 38 scanf("%d%d", &L[i], &R[i]); 39 R[i]++; 40 x[i*2] = L[i]; x[i*2+1] = R[i]; 41 } 42 sort(x, x + n * 2); 43 m = unique(x, x + n * 2) - x; 44 45 memset(covered, false, sizeof(covered)); 46 int ans = 0; 47 for(int i = n - 1; i >= 0; i--) 48 { 49 int qL = lower_bound(x, x + m, L[i]) - x + 1; 50 int qR = lower_bound(x, x + m, R[i]) - x; 51 if(post(1, 1, m, qL, qR)) ans++; 52 } 53 printf("%d ", ans); 54 } 55 56 return 0; 57 }
还有一种方法就是正向模拟，用setv[o]来表示该节点被哪张海报覆盖，此时线段树的功能就是区间替换。
最后查询的时候就看这些节点被哪张海报覆盖，注意有的海报可能会覆盖多个节点，为了避免重复统计，可以用一个bool标记数组。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 20000 + 10; 7 int setv[maxn << 2]; 8 bool is_cnt[maxn]; 9 10 int L[maxn], R[maxn], x[maxn]; 11 int n, m, qL, qR, v, ans; 12 13 void pushdown(int o) 14 { 15 if(setv[o] >= 0) 16 { 17 setv[o*2] = setv[o*2+1] = setv[o]; 18 setv[o] = -1; 19 } 20 } 21 22 void update(int o, int L, int R) 23 { 24 if(qL <= L && qR >= R) { setv[o] = v; return; } 25 pushdown(o); 26 int M = (L + R) / 2; 27 if(qL <= M) update(o*2, L, M); 28 if(qR > M) update(o*2+1, M+1, R); 29 } 30 31 void query(int o, int L, int R) 32 { 33 if(setv[o] >= 0) 34 { 35 if(!is_cnt[setv[o]]) { ans++; is_cnt[setv[o]] = true; } 36 return; 37 } 38 if(L == R) return; 39 int M = (L + R) / 2; 40 query(o*2, L, M); 41 query(o*2+1, M+1, R); 42 } 43 44 int main() 45 { 46 //freopen("in.txt", "r", stdin); 47 48 int T; scanf("%d", &T); 49 while(T--) 50 { 51 scanf("%d", &n); 52 for(int i = 0; i < n; i++) 53 { 54 scanf("%d%d", &L[i], &R[i]); 55 R[i]++; 56 x[i*2] = L[i]; x[i*2+1] = R[i]; 57 } 58 sort(x, x + n * 2); 59 m = unique(x, x + n * 2) - x; 60 61 memset(setv, -1, sizeof(setv)); 62 memset(is_cnt, false, sizeof(is_cnt)); 63 64 for(int i = 0; i < n; i++) 65 { 66 v = i; 67 qL = lower_bound(x, x + m, L[i]) - x + 1; 68 qR = lower_bound(x, x + m, R[i]) - x; 69 update(1, 1, m - 1); 70 } 71 ans = 0; 72 query(1, 1, m - 1); 73 printf("%d ", ans); 74 } 75 76 return 0; 77 }