线段树的基本应用
标签(空格分隔): C++ 数据结构
一.扫描线
1.1引入
有时候我们求一个给定的平面直角坐标系中的N个矩形的面积,而此时,我们就需要引入一种高效且奇妙的算法——扫描线。
例如该图:
1.2分析
我们将其中的矩形按上下边,构建4条扫描线,并按照Y值大小进行排序,并标记为上或下。
但是由于矩形的X坐标有4个,并且相互关联,而想要提升算法效率就必须尽可能规避大的状态转移(区间,信息合并),所以我们将x节点离散化,此时,我们就可以用类似线段树来维护信息。
PS:离散化:进行区间映射,并删除重复(主要用来减少空间大小)
此时,我们用4个不同的x坐标把x轴分成了3段有效的区间.这里要注意我们线段树中每个叶节点控制的是区间[X[L],X[L+1]].线段树中其他节点控制的区间[L,R],也是指的x坐标轴的第L个区间到第R个区间的范围,也就是X[L]到X[R+1]坐标的范围。
考虑如何用此时有效的信息进行最后答案的求值:
1.以Y坐标从小到大的顺序读入每条扫描线
2.记录当前所读入的所有扫描线能有效覆盖X轴的最大长度sum[1].
3.用mark[i]记录线段树中第i个节点是否被完全覆盖,以及完全覆盖次数,当为下位边+1,上位边-1。
建议自己进行模拟,感受一下长度的加减与边上下的关系,同时感受mark的妙用。
1.3 代码实现
建立结构体:(详情看注释)
按节点存储信息
//以横坐标作为线段(区间),对横坐标线段进行扫描
//扫描的作用是每次更新下底边总长度和下底边个数,增加新面积
struct node{//线段
double l,r,h;
int d;
//l: 表示扫描线的左端x坐标
//r:表示扫描线的右端x坐标
//h: 表示扫描线的高度
//d: 为1或-1,标记扫描线是矩形的上位还是下位边.
node(){}
//结构体初始化
node(double x1,double x2,double H,int c):l(x1),r(x2),h(H),d(c){}
//重载运算(相当于cmp)
bool operator<(const node &a)const{
return h<a.h;
}
}s[500005];
- 读入所有矩形的信息,更新扫描线,并且把矩形的两个端点x坐标放入X数组中,
- 对node和X都排序,node按h值从小到大排序.X按从小到大排序.
- 对X数组去重,并且用k表示一共有多少个X.X[i]和X[i+1]表示第i个区间长度.
函数以及变量含义:
- mark: >=0时表示本节点控制的区域内下位边个数-上位边个数的结果.此时可以累加进sum中
- sum: 本节点控制的区域内mark值不为0(大于0)的区域总长度.
线段树操作:
- PushUp(i,l,r): 根据子节点的mark值和sum值更新父节点的mark和sum值,也就是更新自己,由于递归的原因,最终所有的更新都会回到根节点。
- update(ql,qr,d,i,l,r): 使得[ql,qr]与[l,r]区间的公共部分mark值+d.
判断:
ql<=l && r<=qr 且 mark[i]!=0的话:
更新并return
PS:mark[i]不存在-1的情况(如果遍历到了上位边且会使mark[i]-1,那么一定在之前遍历到了相同的下位边使它+1,最小为0的情况)
在一次递归更新左右儿子
最后信息上传(pushup).
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
//mark[i] 表示对于线段树第i个节点是否可以累加进sum,也就是下位边覆盖次数是否大于上位边
//sum[i] 表示对于线段树第i个节点可以成功累加的长度
//X[i] 表示离散化之后的点编号(区间的端点)
const int MAX=1000005;
int mark[MAX<<2];
long long sum[MAX<<2];
long long x[MAX];
//线段
struct seg{
long long l,r,h;
int d;
seg(){}
seg(long long x1,long long x2,long long H,int c):l(x1),r(x2),h(H),d(c){}
bool operator<(const seg &a)const{
return h<a.h;
}
}s[MAX];
void pushup(int n,int left,int right){
if(mark[n])sum[n]=x[right+1]-x[left];
else if(left == right)sum[n]=0;
else sum[n]=sum[n<<1]+sum[n<<1|1];
}
void Update(int L,int R,int d,int n,int left,int right){
//当当前区间被完全覆盖时,直接更新信息,结束
if(L<=left && right<=R){
mark[n]+=d;
pushup(n,left,right);
return;
}
//没有被完全覆盖,向下递归,最后更新信息
int mid=left+right>>1;
if(L<=mid)Update(L,R,d,n<<1,left,mid);
if(R>mid)Update(L,R,d,n<<1|1,mid+1,right);
pushup(n,left,right);
}
//二分查找,在已经更新的X中寻找当前扫描线左右端点的编号(应该是没有-1情况的......)
int search(long long key,long long* x,int n){
int left=0,right=n-1;
while(left<=right){
int mid=left+right>>1;
if(x[mid] == key)return mid;
if(x[mid]>key)right=mid-1;
else left=mid+1;
}
return -1;
}
int main(){
int n,num=0;
long long x1,x2,y1,y2;
cin>>n;
int k=0;
//读入矩形,构造扫描线,更新信息
for(int i=0;i<n;++i){
cin>>x1>>y1>>x2>>y2;
x[k]=x1;
s[k++]=seg(x1,x2,y1,1);
x[k]=x2;
s[k++]=seg(x1,x2,y2,-1);
}
//离散化&去重
sort(x,x+k);
sort(s,s+k);
int m=1;
for(int i=1;i<k;++i)
if(x[i] != x[i-1])
x[m++]=x[i];
long long ans=0;
//根据扫描线的左右端点更新答案
for(int i=0;i<k;++i){
int L=search(s[i].l,x,m);
int R=search(s[i].r,x,m)-1;
Update(L,R,s[i].d,1,0,m-1);
ans+=sum[1]*(s[i+1].h-s[i].h);
}
printf("%lld\n",ans);
return 0;
}