链接:
http://poj.org/problem?id=2528
题目大意:
在长度为10000000的墙上贴海报,海报的高度和墙的高度一样,不同的海报覆盖在不同的区域。如果有重叠位置,则后面贴的海报会把之前贴的海报覆盖掉。问最终有几张海报可以看到?
分析与总结:
又一道成段更新的线段树染色问题来喽。
1. 用map来离散化,结果TLE了。。。然后改用数组存,用二分查询位置,63MS过了,看来以后都不要再用map了。
2. 水过了之后,翻翻傻崽的博客,结果发现自己确实是水过的Orz...主要是离散化会产生一个问题(摘自傻崽博客):
普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了[1,4][1,2][3,4]
线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(str,x) memset(str,(x),sizeof(str))
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define FF(i,n) for(int i=0; i<(n); ++i)
#define mid ((left+right)>>1)
#define len (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
#define STOP puts("Stop Here~");
using namespace std;
const int MAXN = 40005;
int n;
int hash[MAXN<<2],seg[MAXN][2],col[MAXN<<2],vis[MAXN];
inline void push_down(int rt){
if(col[rt]==-1)return;
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
void update(int rt,int left,int right,int l,int r,int data){
if(l<=left && right<=r){
col[rt] = data;
return;
}
if(col[rt]==data) return;
push_down(rt);
int m = mid;
if(l <= m)update(lson,l,r,data);
if(r > m)update(rson,l,r,data);
}
void query(int rt,int left,int right){
if(col[rt]>=0){
vis[col[rt]]=1;
return;
}
if(left!=right && col[rt]==-1) {
int m = mid;
query(lson);
query(rson);
}
}
int binary(int left,int right,int x){
while(left < right){
int m = mid;
if(hash[m] >= x)right=mid;
else left=mid+1;
}
return left;
}
int main(){
int T,l,r;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int pos=0;
FF(i,n){
scanf("%d%d",&l,&r);
seg[i][0]=l;
seg[i][1]=r;
hash[pos++]=l;
hash[pos++]=r;
}
sort(hash,hash+pos);
int kk=1;
FOR(i,1,pos){
if(hash[i]!=hash[i-1])
hash[kk++]=hash[i];
}
//如果相邻数字间距大于1的话,在其中加上任意一个数字
pos = kk;
FOR(i,1,pos){
if(hash[i]-hash[i-1]>1)
hash[kk++] = hash[i-1]+1;
}
sort(hash,hash+kk);
memset(col,-1,sizeof(col));
FF(i,n) {
int a=binary(0,kk,seg[i][0]);
int b=binary(0,kk,seg[i][1]);
++a;++b;
update(1,1,kk,a,b,i);
}
int cnt=0;
mem(vis,0);
query(1,1,kk);
FF(i,kk+1){
if(vis[i]==1)++cnt;
}
printf("%d\n",cnt);
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj-2528 Mayor's posters 测试数据及答案
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 ...
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1739064
POJ题解 个人写法 线段树每个人都不一样
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1746750
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
poj分类poj分类poj分类poj分类