|
|
題目鏈接：http://poj.org/problem?id=2528
  /**//*
 題意：
給定N(N <= 10000)塊木板，依次層疊，問最后能從上方俯視的木板的數(shù)量。
解法：
線段樹（染色問題）
思路：
這題是pku 2777的簡化版，木板的數(shù)量最多10000種，每個(gè)結(jié)點(diǎn)都保存下來
似乎有點(diǎn)力不從心，但是因?yàn)椴迦胧嵌啻危儐栔挥幸淮危晕覀冎灰ＷC
插入是O(logn)的，而詢問可以O(shè)(n)，這樣問題就變得簡單許多，線段樹結(jié)點(diǎn)保存
一個(gè)Cover域，初始化為0，表示是0號(hào)木板（輸入數(shù)據(jù)的木板編號(hào)從1開始），每
次插入時(shí)只更新到完全覆蓋的區(qū)間，如果當(dāng)前結(jié)點(diǎn)的左右兒子的木板顏色不同，
那么它的Cover域就是-1，否則是木板的下標(biāo)。詢問的時(shí)候如果遇到Cover域?yàn)?1
的結(jié)點(diǎn)則遞歸它的子結(jié)點(diǎn)，否則統(tǒng)計(jì)。
 */
#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;
}
|