三，扫描线

利用微积分的思想，将矩形按与X轴垂直的竖线划分，利用线段树维护Y轴上矩形的高，从左到右边扫描，每遇到一条X轴的竖线更新线段树

图片来源网络

1. 扫描线求矩形并集面积
见代码
例题
题目链接： 亚特兰蒂斯

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5 + 10;

int n,m;

struct Segment{
    double x,y1,y2;
    int k;

    bool operator < (const Segment& v)const{
        return x < v.x;
    }
}seg[2 * N];

struct Tree{
    int l,r;
    int cnt;
    double len;
}tr[8 * N];

vector<int> ys;

void pushup(int u){
    if(tr[u].cnt)tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if(tr[u].l == tr[u].r)tr[u].len = 0;
    else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}

void build(int u ,int l,int r){
    if( l == r)tr[u] = {l , r , 0,0};
    else
    {
        tr[u] = {l ,r, 0, 0};
        int mid = l + r >> 1;
        build(u << 1 , l , mid);
        build(u << 1 | 1 , mid + 1 , r);
    }
}

void modify(int u , int l, int r,int k){
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else
    {
        int mid = tr[u].r ++ tr[u].l >> 1;
        if(l <= mid)modify(u << 1 , l ,r , k);
        if(r > mid)modify(u << 1 | 1 , l ,r ,k);
        pushup(u);
    }

}

int main(){

    int T = 1;
    while(cin >> n , n)
    {
        double x1,y1,x2,y2;
        for(int i = 0 ; i < n ; i++)
        {
            cin >> x1 >> y1 >> x2 >> y2;
            ys.push_back(y1),ys.push_back(y2);
            seg[i * 2] = {x1,y1,y2,1};
            seg[i * 2] = {x2 , y1 , y2 , -1};
        }


        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin() , ys.end()) , ys.end());

        build(0 , m - 2);
        sort(seg , seg + 2 * n);

        double res;
        for(int i = 0 ; i < 2 * n ; )
        {
            int j = i;
            while(j <= 2 * n && seg[j].x == seg[i].x)j++;
            if(i)res += tr[1].len * (seg[i].x - seg[i - 1].x);
            while(i < j)
            {
                modify(1,find(seg[i].y1), find(seg[i].y2) - 1 , seg[i].k);
                i++;
            }

        }
        cout << "Test case #" << T++ << endl;
        cout << "Total explored area: " << res << endl << endl; 
    }

    return 0;
}

2. 扫描线求矩形交集最大价值

挖个坑先

例题
题目链接： 窗内的星星
见代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e4 + 10;

struct Tree
{
    int l, r;
    int add,mat;
}tr[8 * N];

struct Segment{
    int x,y1,y2;
    int val;

     bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}a[2 * N];

int n,w,h;
vector<int> ys;

void build(int u , int l ,int r){
    if(l == r)tr[u] = {l ,r, 0,0};
    else
    {
        tr[u] = {l ,r , 0 , 0};
        int mid = l + r >>1;
        build(u << 1 , l , mid);
        build(u << 1 | 1 , mid + 1 , r);
    }
}

void pushup(int u){
    tr[u].mat = max(tr[u << 1].mat, tr[u << 1 | 1].mat);
}

void pushdown(int u){
    if(tr[u].add)
    {
        tr[u << 1].mat += tr[u].add;
        tr[u << 1].add += tr[u].add;
        tr[u << 1 | 1].mat += tr[u].add;
        tr[u << 1 | 1].add += tr[u].add;
        tr[u].add = 0;
    }

}

void change(int u , int l,int r,int c){
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].mat += c,tr[u].add += c;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid)change(u << 1 , l ,r,c);
        if(r > mid)change(u << 1 | 1 , l ,r ,c);
        pushup(u);
    }
}

int find(int x)
{
    return lower_bound(ys.begin() , ys.end() , x) - ys.begin();
}

int main(){
    while(cin >> n >> w >> h)
    {
        memset(tr,0,sizeof(tr));
        memset(a,0,sizeof(a));
        int x,y,c;
        for(int i =0 ; i < n ; i++)
        {
            cin >> x >> y >> c;
            ys.push_back(y) ,ys.push_back(y + h - 1);
            a[i * 2].x = x , a[i * 2].y1 = y , a[i * 2].y2 = y + h - 1 , a[i * 2].val = c;
            a[i * 2 + 1].x = x + w - 1 , a[i * 2 + 1].y1 = y , a[i * 2 + 1].y2 = y + h - 1, a[i * 2 + 1].val = - c;
        }

        sort(ys.begin() , ys.end());
        ys.erase(unique(ys.begin() , ys.end()),ys.end());
        int m = ys.size();
        build(1,1 , m - 2);
        sort(a , a + 2 * n);
        int ans = 0;
        for(int i = 0 ; i < 2 * n ;i++)
        {

            change(1,find(a[i].y1) , find(a[i].y2) - 1 ,a[i].val);
            if(i)ans = max(ans , tr[1].mat);
        }

        cout << ans << endl;
    }


    return 0;
}