本文共 2734 字，大约阅读时间需要 9 分钟。
链接：
题目大意：
在长度为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#include #include #include #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;}
—— 生命的意义，在于赋予它意义士。
原创 ， By D_Double (转载请标明)