用途

• 求矩形面积并，面积交，周长并

思路

• 用一条假想的线从图形的上方扫到下方，分析扫描线被图形截获的线段就能得到所求结果，过程可以用线段树进行加速

面积并

• 从上往下扫，每次扫到和扫描线平行的线就更新线段树
• 线段树一共记录n-1个区间，记录的内容是每个区间被覆盖的次数
• 此时被覆盖的区间数就是当前小矩形的一条边长，而另一条边长则为当前边和下一条边之间的距离
• 有时候坐标很大线段很少，使用离散化

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct L{
    long long x,y1,y2;
    bool flg;
}line[N];
int cnt;
long long seg[N];

long long tree[N*4];
int lazy[N*4];

unordered_map<long long,int> mp;

void build(int p,int l,int r){
    if(l==r){
        tree[p]=0;
        lazy[p]=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
}

void update(int p,int l,int r){
    if(lazy[p]>0) tree[p]=seg[r+1]-seg[l];
    else if(l!=r) tree[p]=tree[p*2]+tree[p*2+1];
    else tree[p]=0;
}


void deal(int p,int l,int r,int x,int y,bool op){
    // cout << p <<' '<< l << ' ' << r << ' ' << x << ' ' << y <<endl;
    if(x<=l&&r<=y){
        lazy[p]+=(op?1:-1);
        update(p,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) deal(p*2,l,mid,x,y,op);
    if(y>mid) deal(p*2+1,mid+1,r,x,y,op);
    update(p,l,r);
}

bool cmp(L a,L b){
    return a.x<b.x;
}


int main(){
    int tst=1;
    int n;
    scanf("%d",&n);
    long long x1,x2,y1,y2;
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        line[++cnt]={x1,y1,y2,1};
        seg[cnt]=y1;
        line[++cnt]={x2,y1,y2,0};
        seg[cnt]=y2;
    }
    sort(line,line+1+cnt,cmp);
    sort(seg,seg+1+cnt);
    int m=unique(seg+1,seg+cnt+1)-(seg+1);
    for(int i=1;i<=m;i++){
        mp[seg[i]]=i;
    }
    m--;
    build(1,1,m);
    long long ans=0;
    for(int i=1;i<cnt;i++){
        int L=mp[line[i].y1];
        int R=mp[line[i].y2]-1;
        deal(1,1,m,L,R,line[i].flg);
        ans+=tree[1]*(line[i+1].x-line[i].x);
    }
    printf("%lld\n",ans);
    return 0;
}

面积交

• 维护lazy大于2

周长并

• 从左往右扫一遍，从上到下扫一遍，每条边都扫
• 每条边获得的答案是abs(tree[1].len-上一次的tree[1].len)