算法竞赛模板

扫描线

离散化后升序扫一遍扫描线
因为每次只需要查询整个区间，不需要查询小区间，所以可以
使用标记永久化，用一个变量统计该区间被覆盖的次数
全覆盖就统计整段长度，否则就从左右儿子统计
注意叶子没有左右儿子要特判一下

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct line {
    int h, l, r, mk;
    bool operator< (const line& b) const {
        return h < b.h;
    }
};

struct node {
    int sum, totlen, l, r;
    node () : sum(0), totlen(0) {}
};

struct seg {
    int n;
    vector<node> tree;
    seg(int _n, vector<int>& b) : n(_n) {
        tree.assign(4*n,node());
        build(1,n,1,b);
    }

    void up(int p, bool leaf) {
        if (tree[p].sum) {
            tree[p].totlen = tree[p].r - tree[p].l;
        } else {
            if (leaf) {
                tree[p].totlen = 0;
            } else {
                tree[p].totlen = tree[p<<1].totlen + tree[p<<1|1].totlen;
            }
        }
    }

    void build(int l, int r, int p, vector<int>& b) {
        if (l == r) {
            tree[p].l = b[l];
            tree[p].r = b[l+1];
            return;
        }
        int mid = l + r >> 1;
        build(l,mid,p<<1, b);
        build(mid+1,r,p<<1|1, b);
        tree[p].l = tree[p<<1].l;
        tree[p].r = tree[p<<1|1].r;
        up(p,0);
    }


    void modify(int ml,int mr, int l, int r, int p, int v) {
        if (r < ml || l > mr) return;
        if (l >= ml && r <= mr) {
            tree[p].sum += v;
            up(p,l==r);
            return;
        }
        int mid = l + r >> 1;
        modify(ml,mr,l,mid,p<<1,v);
        modify(ml,mr,mid+1,r,p<<1|1,v);
        up(p,l==r);
    }
    void modify(int l, int r, int v) {
        modify(l,r,1,n,1,v);
    }
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int>  x(2*n+1);
    vector<line> a(2*n+1);
    for (int i = 1; i <= n; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x[i] = x1;
        x[i+n] = x2;
        a[i] = {y1, x1, x2, 1};
        a[i+n] = {y2, x1, x2, -1};
    }
    sort(x.begin()+1,x.end());
    x.erase(unique(x.begin()+1,x.end()),x.end());
    int tot = x.size() - 1;
    sort(a.begin()+1,a.end());
    seg tree(tot-1,x);
    int ans = 0;
    for (int i = 1; i < 2*n; i++) {
        int nl = lower_bound(x.begin()+1,x.end(),a[i].l) - x.begin();
        int nr = lower_bound(x.begin()+1,x.end(),a[i].r) - x.begin();
        tree.modify(nl,nr-1,a[i].mk);
        ans += tree.tree[1].totlen * (a[i+1].h - a[i].h);
    }
    cout << ans;
    return 0;
}

还有一道，经验乘2
窗口的星星

对于每个星星，都有一个对应的矩形左下角能算贡献

然后用一个区间最值线段树维护扫描线即可
注意如果一个扫描线既有增加的矩形又有减少的矩形，排序时要指定让增加的矩形先统计最值