「洛谷1884」「USACO12FEB」过度种植【离散化扫描线】

佚名 6年前 (2019-04-21) 随笔 701人围观抢沙发百度已收录

题目链接

【洛谷传送门】

题解

矩阵面积的并模板。（请求洛谷加为模板题）
很明显是要离散化的。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们将矩阵与\(x\)轴平行的两个线段取出来。并且将这两个端点的\(x1\)和\(x2\)进行离散化。
因为每一次我们都会对当前的这一层的某一段线段进行操作，那么就用权值线段树维护是否存在。

这个只是矩阵面积的并。
还有加强版：【HDU 1542】
还有矩阵面积的交。

代码

#include <bits/stdc++.h>
#define gc getchar
#define lc (nod << 1)
#define rc (nod << 1 | 1)
using namespace std;
typedef long long ll;
const int N = 2003;
template <typename T> void read(T &x) {
    x = 0; T fl = 1; char c = 0;
    for (; c < '0' || c > '9'; c = gc()) 
        if (c == '-') fl = -1;
    for (; c >= '0' && c <= '9'; c = gc()) 
        x = (x << 1) + (x << 3) + (c ^ 48);
    x *= fl;
}
struct E{ int l, r, h, d; } ed[N * 2];
bool cmp_sl(E x, E y) { return x.h < y.h; }
ll ans = 0ll; 
int n, dcnt;
int disc[N];
struct seg { ll s, tag; } tr[N << 2];
void pushup(int nod, int l, int r) {
    if (tr[nod].tag) tr[nod].s = disc[r + 1] - disc[l];
    else if (l == r) tr[nod].s = 0;
    else tr[nod].s = tr[lc].s + tr[rc].s; 
}
void upd(int nod, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        tr[nod].tag += val;
        pushup(nod, l, r); 
        return; 
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) upd(lc, l, mid, ql, qr, val);
    if (qr > mid) upd(rc, mid + 1, r, ql, qr, val); 
    pushup(nod, l, r); 
}
int main() {
    read(n);  
    for (int i = 1, x1, y1, x2, y2; i <= n; i ++) {
        read(x1); read(y1); read(x2); read(y2); 
        disc[++ dcnt] = x1; ed[dcnt] = (E){x1, x2, y1, 1}; 
        disc[++ dcnt] = x2; ed[dcnt] = (E){x1, x2, y2, -1};
    }
    sort(disc + 1, disc + 1 + dcnt); 
    sort(ed + 1, ed + 1 + dcnt, cmp_sl);
    int m = unique(disc + 1, disc + 1 + dcnt) - disc - 1;
    for (int i = 1; i < dcnt; i ++) {
        int l = lower_bound(disc + 1, disc + 1 + m, ed[i].l) - disc;
        int r = lower_bound(disc + 1, disc + 1 + m, ed[i].r) - disc;
        if (l < r) upd(1, 1, m, l, r - 1, ed[i].d); 
        ans += tr[1].s * (ed[i + 1].h - ed[i].h); 
    }
    cout << ans << endl; 
    return 0; 
}