一、基本概念
线段树:线段树基本概念
离散化:把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。
例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};
二、算法
思想:
- 记录每个点的左端和右端,全部保存到一个数组a中并排序
- 节点去重
- 如果两个节点间距离大于1,添加一个中间节点
- 再次对a排序
- 在a中二分搜索原来每个点的左右端,将索引值保存在线段树中
C++版本一
scanf("%d",&n);
int cnt = 0,len = 1;
for(i=1;i<=n;i++)//记录头尾
{
sf("%d %d",&s1[i],&s2[i]);
a[++cnt] = s1[i];
a[++cnt] = s2[i];
}
sort(a+1,a+1+cnt);
for(i=2;i<=cnt;i++)//去重
{
if(a[i]!=a[i-1]) a[++len] = a[i];
}
for(i=len;i>1;i--)//添加中间值
{
if(a[i]-a[i-1]>1) a[++len] = a[i]-1;
}
sort(a+1,a+1+len);
for(i=1;i<=n;i++)
{
int l = BSearch(1,len,s1[i]);
int r = BSearch(1,len,s2[i]);
update(i,l,r,1,len,1);
}
三、例题
http://poj.org/problem?id=2528(题解:https://blog.csdn.net/weixin_43272781/article/details/83420707)
http://acm.hdu.edu.cn/showproblem.php?pid=1199(题解:https://blog.csdn.net/weixin_43272781/article/details/83653497)