|
|
题目链接：http://poj.org/problem?id=2528
  /**//*
 题意：
给定N(N <= 10000)块木板，依次层叠，问最后能从上方俯视的木板的数量。
解法：
线段树（染色问题）
思路：
这题是pku 2777的简化版，木板的数量最多10000种，每个结点都保存下来
似乎有点力不从心，但是因为插入是多次，而询问只有一次，所以我们只要保证
插入是O(logn)的，而询问可以O(n)，这样问题就变得简单许多，线段树结点保存
一个Cover域，初始化为0，表示是0号木板（输入数据的木板编号从1开始），每
次插入时只更新到完全覆盖的区间，如果当前结点的左右儿子的木板颜色不同，
那么它的Cover域就是-1，否则是木板的下标。询问的时候如果遇到Cover域为-1
的结点则递归它的子结点，否则统计。
 */
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
int tmp[maxn], tmpsize;
int bin[maxn], size;
struct Interval  {
int l, r;
}I[maxn];
struct Tree {
int nCover;
int son[2];
  void clear() {
son[0] = son[1] = -1;
nCover = 0;
 }
}T[ maxn*4 ];
int root, tot = 0;
int GetId(int& root) {
if(root == -1) {
root = tot++;
T[root].clear();
}
return root;
}
void Discretization() {
sort(tmp, tmp + tmpsize);
bin[ size = 1 ] = tmp[0];
int i;
for(i = 1; i < tmpsize; i++) {
if(tmp[i] != tmp[i-1])
bin[ ++size ] = tmp[i];
}
}
int Binary(int v) {
int l = 1;
int r = size;
while(l <= r) {
int m = (l + r) >> 1;
if(bin[m] == v)
return m;
if(v > bin[m]) {
l = m + 1;
}else
r = m - 1;
}
}
int hash[ maxn ], Case;
void Insert(int& root, int nl, int nr, int l, int r, int val) {
if(nl > r || nr < l)
return ;
GetId(root);
if(nl <= l && r <= nr) {
T[root].nCover = val;
return ;
}
if(T[root].nCover != -1) {
int i;
for(i = 0; i < 2; i++) {
int idx = GetId(T[root].son[i]);
T[idx].nCover = T[root].nCover;
}
T[root].nCover = -1;
}
int mid = (l + r) >> 1;
Insert(T[root].son[0], nl, nr, l, mid, val);
Insert(T[root].son[1], nl, nr, mid+1, r, val);
}
void Query(int root, int l, int r) {
if(root == -1)
return ;
if(T[root].nCover != -1) {
hash[ T[root].nCover ] = Case;
return ;
}
int mid = (l + r) >> 1;
Query(T[root].son[0], l, mid);
Query(T[root].son[1], mid+1, r);
}
int main() {
int t, i;
int n;
scanf("%d", &t);
while(t--) {
Case ++;
tmpsize = 0;
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d %d", &I[i].l, &I[i].r);
tmp[ tmpsize ++ ] = I[i].l;
tmp[ tmpsize ++ ] = I[i].r;
}
Discretization();
root = -1;
tot = 0;
for(i = 0; i < n; i++) {
I[i].l = Binary(I[i].l);
I[i].r = Binary(I[i].r);
//printf("<%d %d>\n", I[i].l, I[i].r);
Insert(root, I[i].l, I[i].r, 1, size, i+1);
}
int nCount = 0;
Query(root, 1, size);
for(i = 1; i <= size; i++) {
if(hash[i] == Case)
nCount ++;
}
printf("%d\n", nCount);
}
return 0;
}
|