http://poj.org/problem?id=2528
题目大意是市长竞选要贴海报,给出墙的长度和依次张贴的海报的长度区间(参考题目给的图),问最后你能看见的海报有几张
就是有的先贴的海报可能会被后贴的海报完全盖住,那就看不见了
这里就非常抽象的区间更新,墙的长度为建立线段树的总区间,每贴一张海报代表将这个区间的颜色涂为相应的,每张海报的颜色当然
都不相同,求最后又多少种颜色就行,但这里还要用到基础的离散化
离散化是把无限空间中无限的个体映射到有限的空间中去，以此提高算法的时空效率。
简单点说,假设区间长度有一亿甚至跟多,但是区间里具体的值却最多只用到了一百万,且不说能否开那么大的数组,也造成了
内存的浪费,所以用离散化来节省不必要的浪费
举这个题目的样例来说(前三个)
如果只是改变区间1 7 2 6 8 10的颜色,那么剩下的数字并没有用到
那么我们将这些数字排序,x[1]=1 x[2]=2 x[3]=6 x[4]=7 x[5]=8 x[6]=10
但是如果每个相邻的差值大于1的时候要插入一个数(就插入x[i]-1好了),
(如果不插的话
假设三张海报为：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)
插入后新的排序为x[1]=1 x[2]=2 x[3]=5 x[4]=6 x[5]=7 x[6]=8 x[7]=9 x[8]=10
然后以这个新的长度为8的数组区间建树就好
code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point {
int l,r;
int mark,sum;
};
point tree[**],num[*];
int ans,res[*],visit[*];
void build(int i,int left,int right)
{
tree[i].l=left,tree[i].r=right;
tree[i].mark=tree[i].sum=;
if (left==right) return ;
int mid=(left+right)/;
build(i*,left,mid);
build(i*+,mid+,right);
}
void update(int i,int left,int right,int val)
{
if (left<=tree[i].l&&tree[i].r<=right){tree[i].mark=tree[i].sum=val;return ;}
if (tree[i].mark)
{
tree[i*].mark=tree[i*+].mark=tree[i].mark;
tree[i*].sum=tree[i*+].sum=tree[i].mark;
tree[i].mark=;
}
int mid=(tree[i].r+tree[i].l)/;
if (left>mid) update(i*+,left,right,val);
else if (right<=mid) update(i*,left,right,val);
else
{
update(i*,left,mid,val);
update(i*+,mid+,right,val);
}
}
int find(int i)
{
if (tree[i].l==tree[i].r)
{
if (!visit[tree[i].sum])
{
visit[tree[i].sum]=;
++ans;
}
return ans;
}
if (tree[i].mark)
{
tree[i*].mark=tree[i*+].mark=tree[i].mark;
tree[i*].sum=tree[i*+].sum=tree[i].mark;
tree[i].mark=;
}
find(i*);
find(i*+);
}
int main()
{
int t,i,n,tn,tn1,powr,powl;
scanf("%d",&t); if (t==) return ;
while (t--)
{
res[]=;
scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d %d",&num[i].l,&num[i].r);
if (num[i].l>num[i].r) swap(num[i].l,num[i].r);
res[++res[]]=num[i].l;
res[++res[]]=num[i].r;
}
sort(res+,res+res[]+);//离散化
tn1=tn=unique(res+,res+res[]+)-res;
for (i=;i<tn;i++)//插入数
if (res[i]-res[i-]>)
res[tn1++]=res[i]-;
res[]=tn1-;
sort(res+,res+res[]+);
build(,,res[]);//以新的区间建树
for (i=;i<=n;i++)
{
powl=lower_bound(res+,res++res[],num[i].l)-res;
powr=lower_bound(res+,res++res[],num[i].r)-res;
update(,powl,powr,i);
}
ans=;
memset(visit,,sizeof(visit));
visit[]=;
printf("%d\n",find());
} return ;
}