离散化其实就是把所有端点放在一起，然后排序去个重就好了。
比如说去重以后的端点个数为m，那这m个点就构成m-1个小区间。然后给这m-1个小区间编号1~m-1，再用线段树来做就行了。
具体思路是，从最后一张的海报来判断，如果海报覆盖的区域有空白区域那么这张海报就是可见的。并及时更新线段树信息。
说一个我调了很久的才发现小错误，比如书2 2这样一个海报，如果你把这张海报的左右端点都记作2的话那就是个空区间了。
其实，这张海报覆盖的是第2块瓷砖。所以R++，2 3就表示第2块瓷砖的左右端点。
当然，如果不是我这个思路，就可能不会出现这个问题。
这个是跟着去年北大的ACM培训班上给的标程写的，指针满天飞，个人感觉代码不够简洁。
//#define LOCAL
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; int n;
struct CPost
{
int L, R;
}posters[ + ];
int x[ + ]; //海报的端点瓷砖编号
int hash[ + ];//hash[i]表示瓷砖i所处的离散化后的区间编号 struct CNode
{
int L, R;
bool bCovered; //区间[L, R]是否已经完全覆盖
CNode *pLeft, *pRight;
}Tree[];
int nNodeCount = ;
int Mid(CNode* pRoot)
{
return (pRoot->L + pRoot->R) / ;
}
void BuildTree(CNode *pRoot, int L, int R)
{
pRoot->L = L;
pRoot->R = R;
pRoot->bCovered = false;
if(L == R)
return;
++nNodeCount;
pRoot->pLeft = Tree + nNodeCount;
++nNodeCount;
pRoot->pRight = Tree + nNodeCount;
BuildTree(pRoot->pLeft, L, (L+R)/);
BuildTree(pRoot->pRight, (L+R)/+, R);
}
bool Post(CNode *pRoot, int L, int R)
{//插入一张覆盖区间[L, R]的海报，返回true则说明该区间是部分或者全部可见的
if(pRoot->bCovered)
return false;
if(pRoot->L == L && pRoot->R == R)
{
pRoot->bCovered = true;
return true;
}
bool bResult;
if(R <= Mid(pRoot))
bResult = Post(pRoot->pLeft, L, R);
else if(L >= Mid(pRoot) + )
bResult = Post(pRoot->pRight, L, R);
else
{
bool b1 = Post(pRoot->pLeft, L, Mid(pRoot));
bool b2 = Post(pRoot->pRight, Mid(pRoot) + , R);
bResult = b1 || b2;
}
//要更新的节点的覆盖情况
if(pRoot->pLeft->bCovered && pRoot->pRight->bCovered)
pRoot->bCovered = true;
return bResult;
} int main(void)
{
#ifdef LOCAL
freopen("2528in.txt", "r", stdin);
#endif
int t;
int i, j, k;
scanf("%d", &t);
int nCaseNo = ;
while(t--)
{
++nCaseNo;
scanf("%d", &n);
int nCount = ;
for(i = ; i < n; ++i)
{
scanf("%d%d", &posters[i].L, &posters[i].R);
x[nCount++] = posters[i].L;
x[nCount++] = posters[i].R;
}
sort(x, x + nCount);
nCount = unique(x, x + nCount) - x;//元素去重
//将下面离散化
int nIntervalNo = ;
for(i = ; i < nCount; ++i)
{
hash[x[i]] = nIntervalNo;
if(i < nCount - )
{
if(x[i + ] - x[i] == )
++nIntervalNo;
else
nIntervalNo += ;
}
} BuildTree(Tree, , nIntervalNo);
int nSum = ;
for(i = n - ; i >= ; --i)
{//从后往前遍历每个海报是否可见
if(Post(Tree, hash[posters[i].L], hash[posters[i].R]))
++nSum;
}
printf("%d\n", nSum);
}
return ;
}
代码君
自己改成数组的写法，感觉可读性要好很多。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int covered[maxn << ];
int n, m, L[maxn], R[maxn], x[maxn]; bool post(int o, int L, int R, int qL, int qR)
{
if(covered[o]) return false;
if(qL == L && qR == R) { covered[o] = true; return true; }
int M = (L + R) / ;
bool ok;
if(qR <= M) ok = post(o*, L, M, qL, qR);
else if(qL > M) ok = post(o*+, M+, R, qL, qR);
else
{
bool ok1 = post(o*, L, M, qL, M);
bool ok2 = post(o*+, M+, R, M+, qR);
ok = ok1 || ok2;
}
if(covered[o*] && covered[o*+]) covered[o] = true;
return ok;
} int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ; i < n; i++)
{
scanf("%d%d", &L[i], &R[i]);
R[i]++;
x[i*] = L[i]; x[i*+] = R[i];
}
sort(x, x + n * );
m = unique(x, x + n * ) - x; memset(covered, false, sizeof(covered));
int ans = ;
for(int i = n - ; i >= ; i--)
{
int qL = lower_bound(x, x + m, L[i]) - x + ;
int qR = lower_bound(x, x + m, R[i]) - x;
if(post(, , m, qL, qR)) ans++;
}
printf("%d\n", ans);
} return ;
}
代码君
还有一种方法就是正向模拟，用setv[o]来表示该节点被哪张海报覆盖，此时线段树的功能就是区间替换。
最后查询的时候就看这些节点被哪张海报覆盖，注意有的海报可能会覆盖多个节点，为了避免重复统计，可以用一个bool标记数组。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int setv[maxn << ];
bool is_cnt[maxn]; int L[maxn], R[maxn], x[maxn];
int n, m, qL, qR, v, ans; void pushdown(int o)
{
if(setv[o] >= )
{
setv[o*] = setv[o*+] = setv[o];
setv[o] = -;
}
} void update(int o, int L, int R)
{
if(qL <= L && qR >= R) { setv[o] = v; return; }
pushdown(o);
int M = (L + R) / ;
if(qL <= M) update(o*, L, M);
if(qR > M) update(o*+, M+, R);
} void query(int o, int L, int R)
{
if(setv[o] >= )
{
if(!is_cnt[setv[o]]) { ans++; is_cnt[setv[o]] = true; }
return;
}
if(L == R) return;
int M = (L + R) / ;
query(o*, L, M);
query(o*+, M+, R);
} int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ; i < n; i++)
{
scanf("%d%d", &L[i], &R[i]);
R[i]++;
x[i*] = L[i]; x[i*+] = R[i];
}
sort(x, x + n * );
m = unique(x, x + n * ) - x; memset(setv, -, sizeof(setv));
memset(is_cnt, false, sizeof(is_cnt)); for(int i = ; i < n; i++)
{
v = i;
qL = lower_bound(x, x + m, L[i]) - x + ;
qR = lower_bound(x, x + m, R[i]) - x;
update(, , m - );
}
ans = ;
query(, , m - );
printf("%d\n", ans);
} return ;
}
代码君