Description
Input
Output
Sample Input
1 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
Source
思路：先离散化一下，把区间
1 4 2 6 8 10 3 4 7 10
处理成
1 4 2 5 7 8 3 4 6 8再用线段树维护每个区间的颜色值，每个海报对应一种不同的颜色值。
#include <cstdio>
#include <algorithm>
using namespace std;
struct{
int l,r;
}q[10000];
struct H{ //用于离散化，id表示在原来的哪个海报，pos为0表示海报中的l,为1表示海报中的r
int val,id,pos;
}h[20000];
int color[80000];
bool vis[10001];
bool cmp(struct H a,struct H b)
{
return a.val<b.val;
}
void build(int idx,int s,int e)
{
if(s!=e)
{
int mid=(s+e)>>1;
build(idx<<1,s,mid);
build(idx<<1|1,mid+1,e);
}
color[idx]=0;//所有节点的颜色值初始化为0
}
void add(int idx,int s,int e,int l,int r,int val)
{
if(s==l && e==r)//如果区间相同则直接更改颜色值
{
color[idx]=val;
return;
}
if(color[idx] && color[idx]!=val)//如果有颜色并且颜色值不同则把颜色值赋给儿子节点并且将自己置零
{
color[idx<<1]=color[idx];
color[idx<<1|1]=color[idx];
color[idx]=0;
}
int mid=(s+e)>>1;
if(r<=mid) add(idx<<1,s,mid,l,r,val);//在儿子
else if(l>mid) add(idx<<1|1,mid+1,e,l,r,val);//在右儿子
else//两边都有
{
add(idx<<1,s,mid,l,mid,val);
add(idx<<1|1,mid+1,e,mid+1,r,val);
}
}
int query(int idx)
{
if(color[idx])//以有颜色作为递归边界，因为离散化处理之后再add肯定不会存在从根节点到叶子节点都没有颜色值的情况
{
if(!vis[color[idx]])
{
vis[color[idx]]=1;
return 1;
}
return 0;
}
return query(idx<<1)+query(idx<<1|1);
}
int main()
{
int T,n,i,last,total;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
h[i*2].val=q[i].l;
h[i*2].id=i;
h[i*2].pos=0;
h[i*2+1].val=q[i].r;
h[i*2+1].id=i;
h[i*2+1].pos=1;
}
//离散化
sort(h,h+n*2,cmp);
last=-1;
total=0;
for(i=0;i<n*2;i++)
{
if(h[i].val!=last)
{
total++;
if(h[i].val!=total)
{
if(h[i].pos) q[h[i].id].r=total;
else q[h[i].id].l=total;
}
last=h[i].val;
}
else
{
if(h[i].val!=total)
{
if(h[i].pos) q[h[i].id].r=total;
else q[h[i].id].l=total;
}
}
}
//离散化完成
for(i=0;i<=n;i++) vis[i]=0;
build(1,1,total);
for(i=0;i<n;i++)
{
add(1,1,total,q[i].l,q[i].r,i+1);
}
printf("%d\n",query(1));
}
}
POJ-2528-Mayor's posters(线段树),布布扣,bubuko.com
原文：http://blog.csdn.net/faithdmc/article/details/36892761