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