题意:

在一面长度为10000000 的墙上贴广告,告诉你每张海报的l,r(1 <= l <= ri <= 10000000.),让你求最后有几张海报露出来

链接:http://poj.org/problem?id=2528

思路:

由于数据较大,直接开数组不现实,所以我们考虑将每个点离散化,由于这里可能存在原本不相邻的点在离散化后变成相邻

例如三张海报分别为1-5,1-2,4-5,将数据离散化后1,2,4,5分别对应1,2,3,4,此时我们发现用离散化之后的数据得出来的结果

是2,但是实际上可以看到的海报为3,所以当a[i]-a[i-1]>1时,我们要再加入a[i-1]+1,这样就能避免上述情况。

所以,这道题就变成了离散化+线段树区间染色

代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <map>
using namespace std;
const int MAXN=5e4+;
typedef long long ll;
int l_[MAXN],r_[MAXN],lsh[MAXN<<],visit[MAXN],lazy[MAXN<<];
void push_down(int node)
{
lazy[node<<]=lazy[node];
lazy[node<<|]=lazy[node];
lazy[node]=;
}
void update(int node,int l,int r,int x,int y,int k)
{
if(x<=l&&y>=r)
{
lazy[node]=k;
return;
}
if(lazy[node])
push_down(node);
int mid=(l+r)>>;
if(x<=mid)
update(node<<,l,mid,x,y,k);
if(y>mid)
update(node<<|,mid+,r,x,y,k);
}
int ans=;
void query(int node,int l,int r,int x,int y)
{
if(lazy[node])
{
if(!visit[lazy[node]])
ans++,visit[lazy[node]]=;
return;
}
if(l==r)
return;
int mid=(l+r)>>;
if(x<=mid)
query(node<<,l,mid,x,y);
if(y>mid)
query(node<<|,mid+,r,x,y);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(lazy,,sizeof(lazy));
memset(visit,,sizeof(visit));
ans=;
int n;
scanf("%d",&n);
int index=;
for(int i=; i<=n; i++)
{
scanf("%d%d",&l_[i],&r_[i]);
lsh[index++]=l_[i],lsh[index++]=r_[i];
}
sort(lsh,lsh+index);
int temp=index;
for(int i=; i<temp; i++)
if(lsh[i]-lsh[i-]>)
lsh[index++]=lsh[i-]+;
int cnt=unique(lsh,lsh+index)-lsh;
for(int i=; i<=n; i++)
{
l_[i]=lower_bound(lsh,lsh+cnt,l_[i])-lsh+;
r_[i]=lower_bound(lsh,lsh+cnt,r_[i])-lsh+;
update(,,cnt,l_[i],r_[i],i);
}
query(,,cnt,,cnt);
printf("%d\n",ans);
}
return ;
}
05-22 01:02