题解 P5490 【【模板】扫描线】

· · 题解

为啥要离散化啊。。多麻烦。。。

这里提供一种偷懒的做法：

动态开点线段树+标记永久化， 就可省略掉离散化啦！

大概的思路和其他的题解差不多， 这里就不赘述了， 下面提供做法的实现， 主要在注释中说明。

#include <bits/stdc++.h>

using namespace std;

#define ge getchar()
#define Re read()

inline int read() {
    int x = 0, ch;
    while(!isdigit(ch = ge)) ;
    while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
    return x;
}

const int MAXN = 200100;

struct Node {
    int l, r, p;

    Node() {}
    Node(int l, int r, int p):l(l), r(r), p(p) {}

    friend bool operator < (Node a, Node b) { return a.p < b.p; }
}Ins[MAXN + 1], Del[MAXN + 1];

struct Segment_Tree { // 下面是线段树
    #define ls T[x].r
    #define rs T[x].l

    struct Node { int l, r, sum, tg; } T[MAXN << 6]; // 每一次修改最多修改的点数有log级别， 所以动态开点要乘log（最好再乘2）
    int ct;

    inline void pushup(int x, int l, int r) {
        if(T[x].tg) T[x].sum = r - l + 1; // 如果这个点上有标记， 那么就说明被线段覆盖了， 长度就是 r-l+1
        else T[x].sum = T[ls].sum + T[rs].sum; // 没有标记就从线段树上的两个儿子节点继承
    }
// 没有pushdown 标记永久化节省空间
    inline void Modify(int&x, int l, int r, int L, int R, int v) {
        if(!x) x = ++ct; // 动态开点
        if(L <= l && r <= R) {
            T[x].tg += v; // 更新标记
            pushup(x, l, r); // 更新节点值
            return ;
        } int mid = (l + r) >> 1;
        if(L <= mid) Modify(ls, l, mid, L, R, v);
        if(mid < R) Modify(rs, mid + 1, r, L, R, v);
        pushup(x, l, r); // 别忘了更新
    }

    inline int Query() { return T[1].sum; } // 询问沿y轴截线段的长度和， 相当于是线段树的1号节点存的长度和。

    #undef ls
    #undef rs
}seg; // 上面是线段树

int main() {
    int n = Re, mi = 1e9, mx = 0;
    for(int i = 1; i <= n; i++) {
        int lx = Re, ly = Re, rx = Re, ry = Re;
        Ins[i] = Node(ly, ry, lx);
        Del[i] = Node(ly, ry, rx);
        mi = min(mi, ly);
        mx = max(mx, ry);
    } int rt = 0; long long res = 0;
    sort(Ins + 1, Ins + 1 + n); Ins[n + 1] = Node(0, 0, 2e9);
    sort(Del + 1, Del + 1 + n); Del[n + 1] = Node(0, 0, 2e9);
    for(int i = 1, a = 1, b = 1, N = n << 1, las = 0; i <= N; i++) {
        int x = min(Ins[a].p, Del[b].p);
        res += 1LL * (x - las) * seg.Query(), las = x; // 求出上次询问的横坐标差 * 当前扫描线上的沿y轴的截线段长度和。
        if(Ins[a].p == x) seg.Modify(rt, mi, mx, Ins[a].l, Ins[a].r - 1, 1), ++a; // 如果当前这个x坐标需要插入一条线段， 那么就+1
        else seg.Modify(rt, mi, mx, Del[b].l, Del[b].r - 1, -1), ++b; // 如果删除就-1
        //这一段为啥要将r-1呢？ 因为线段树里头的线段默认计算的长度为 r-l+1， 这个时候我们把r-1之后才符合计算面积的公式， 而且所有插入的线段的r都减了1之后计算并集并不会影响。
    } printf("%lld\n", res);
    return 0; // 完结撒花
} // 没有离散化真清爽啊（雾）