POJ 2528 (线段树+离散化) Mayor's posters

  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\n", nSum);
110     }
111     return 0;
112 }