POJ - 2528 （离散化+线段树区间覆盖）

Description

Input

Output

For each input data set print the number of visible posters after all the posters are placed. 

The picture below illustrates the case of the sample input. 

Sample Input

1
5
1 4
2 6
8 10
3 4
7 10

Sample Output

4

题意：贴海报，海报可以覆盖，会给出你每张海报的长款，然后问你最后还能看到几张海报。

我做这道题遇到的坑点，第一点离散化，第二点线段树用的不熟练，在update和pushdown出错了，区间覆盖和区间更新有一点点不一样就是，你要把根节点变回-1，还有就是用的太少了，理解不够update左右儿子更新出错了。

离散化的话我也是看了别人的博客：点击打开链接

引用大佬博客：

解法：离散化，如下面的例子（题目的样例），因为单位1是一个单位长度，将下面的

      1   2   3   4  6   7   8   10

     —  —  —  —  —  —  —  —

      1   2   3   4  5   6   7   8

离散化  X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] = 8; X[8] = 10

于是将一个很大的区间映射到一个较小的区间之中了，然后再对每一张海报依次更新在宽度为1~8的墙上(用线段树），最后统计不同颜色的段数。

但是只是这样简单的离散化是错误的，

如三张海报为：1~10 1~4 6~10

离散化时 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一张海报时：墙的1~4被染为1；
第二张海报时：墙的1~2被染为2，3~4仍为1；
第三张海报时：墙的3~4被染为3，1~2仍为2。
最终，第一张海报就显示被完全覆盖了，于是输出2，但实际上明显不是这样，正确输出为3。

新的离散方法为：在相差大于1的数间加一个数，例如在上面1 4 6 10中间加5（算法中实际上1，4之间，6，10之间都新增了数的）

X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10

这样之后，第一次是1~5被染成1；第二次1~2被染成2；第三次4~5被染成3

最终，1~2为2，3为1，4~5为3，于是输出正确结果3。

#include<math.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=10005;
int n;
int vis[maxn<<3],sum[maxn<<4];
int li[maxn*2],ri[maxn*2],lsh[maxn<<2];
void pushdown(int rt)
{
sum[rt<<1]=sum[rt];
sum[rt<<1|1]=sum[rt];
sum[rt]=-1;
}
void update(int L,int R,int C,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
sum[rt]=C;
return ;
}
if(sum[rt]!=-1)
pushdown(rt);
int m=(l+r)>>1;
if(m>=R) update(L,R,C,l,m,rt<<1);
else if(L>m) update(L,R,C,m+1,r,rt<<1|1);
else update(L,m,C,l,m,rt<<1),update(m+1,R,C,m+1,r,rt<<1|1);
}
int ans;
void query(int l,int r,int rt)
{
if(!vis[sum[rt]]&&sum[rt]!=-1)
{
ans++;
vis[sum[rt]]=1;
return ;
}
if(l==r)
{
return ;
}
if(sum[rt]!=-1)
pushdown(rt);
int m=(l+r)>>1;
query(l,m,rt<<1);
query(m+1,r,rt<<1|1);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(sum,-1,sizeof(sum));
memset(vis,0,sizeof(vis));
int tot=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&li[i],&ri[i]);
lsh[tot++]=li[i];
lsh[tot++]=ri[i];
}
sort(lsh,lsh+tot);
int mm=unique(lsh,lsh+tot)-lsh;
int tt=mm;
for(int i=1;i<tt;i++)
{
if(lsh[i]-lsh[i-1]>1)
lsh[mm++]=lsh[i-1]+1;
}
sort(lsh,lsh+mm);
for(int i=0;i<n;i++)
{
int x=lower_bound(lsh,lsh+mm,li[i])-lsh;
int y=lower_bound(lsh,lsh+mm,ri[i])-lsh;
update(x,y,i,0,mm-1,1);
}
ans=0;
query(0,mm-1,1);
printf("%dn",ans);
}
}

最后

以上就是小巧冰棍为你收集整理的POJ - 2528 （离散化+线段树区间覆盖）的全部内容，希望文章能够帮你解决POJ - 2528 （离散化+线段树区间覆盖）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。