扫描线小复习

扫描线

• 扫描线
  • 思想
  • 实现

思想

扫描线的思想十分简单，就是把矩形分为多次小的矩形求解罢了，关键在于实现
记得有一次周考就写挂了......

实现

首先想要正好不重不漏地扫过一个矩形（只有一个的情况下）而不影响其他非矩形地方的方法是什么？
假设我扫描线是从下往上扫的，那么对于这个矩形而言，我在遇到下边的时候权值+1,遇到上边时权值-1
为了保证左侧和右侧不会扫过头（不会扫过其宽度），那么我应该维护这个线段区间权值+1-1.
为了求解面积，我不可忽略这个矩形的高度，换句话说，这个状态应该是持续性的（扫描有过程），而持续的时间就是高度
而这种区间的维护我可以利用线段树完成

现在扩展到有重叠的多个矩形，发现如果+1这样的话，可能某些区间会达到2/3/4等等等等，但是面积我应该只计算1
所以我线段树中应该维护两个值：重叠次数和贡献
贡献只有0/1之分，而重叠次数可以有很多
当且仅当重叠次数=0时，贡献为0
差不多就行了吧，注意排序即可。
然后离散化的话，就需要一个映射关系
例如在线段树上节点x对应[X[tree[x].l],X[tree[x].r+1]]这条横边

代码：

#include <bits/stdc++.h>
//#define int long long
using namespace std;
struct xd{
	long long l;
	long long r;
	long long hi;
	long long lz;//表示上边或下边 
}line[1000005];
struct node {
    long long sum;  //（被覆盖的次数 
    long long l;
    long long r;
    long long len;//表示长度（被截取后 ，即实际有效长度 
} tree[4000005];
long long X[1000005];
void build(long long rt,long long l,long long r){
	tree[rt].l=l;
	tree[rt].r=r;
    if(l==r){
    	return;
	}
    long long mid = (l + r) >> 1;
    build(rt*2, l, mid);
    build(rt*2+1, mid + 1, r);
    return;
} 
bool cmp(xd x,xd y){
	if(x.hi!=y.hi)return x.hi<y.hi;
	else return x.l<y.l;
}
void pushup(long long rt) {
    int l = tree[rt].l, r = tree[rt].r;
    if(tree[rt].sum)
    	tree[rt].len=X[r+1]-X[l];//实际长度 ，只要不为零，说明对整个面积有贡献，是被全部覆盖的  
    else
        tree[rt].len=tree[rt*2].len+tree[rt*2+1].len;//可能存在被部分覆盖的情况，需要看儿子的贡献 
}
void updata(int rt,long long L,long long R,long long c) {
    int l=tree[rt].l;
	int r=tree[rt].r;
    if(X[r+1]<=L||R<= X[l])
        return;
    if(L<=X[l]&&X[r+1]<= R) {
        tree[rt].sum+=c;
        pushup(rt);
        return;
    }
    updata(rt*2, L, R, c);
    updata(rt*2+1, L, R, c);
    pushup(rt);
}
int main() {
	ios::sync_with_stdio(false);
	long long n;
	cin >> n;
	for(long long i=1;i<=n;i++){
		long long a,b,c,d;
		cin >> a>> b>> c>> d; 
		X[i*2-1]=a;
		X[i*2]=c;
		line[i*2-1]=(xd){a,c,b,1};
		line[i*2]=(xd){a,c,d,-1};
	}
    n<<=1;
    sort(X+1,X+1+n);
    sort(line+1,line+1+n,cmp);
    int tot = unique(X + 1, X + n + 1) - X - 1;//去重，tot表示去重后的个数
	//补充下，unique(a,b)-a表示找a-b的非重复个数，并更新去重的数组；(大概？ 
	build(1,1,tot-1);//右边的没了 
	long long ans=0;
	for(int i=1;i<n;i++){
		updata(1,line[i].l,line[i].r,line[i].lz);
        ans+=tree[1].len*(line[i + 1].hi-line[i].hi);
//        cout<<ans<<endl;
	}
	cout<<ans;
}