扫描线

本文主要是介绍扫描线，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

扫描线

焯，我tm以为这玩意很高深，看了半天，tm很简单

核心就是我们要求一堆矩形的面积并or周长和，直接标记vis的话，我们的数组得开到 \(10^9 \times 10^9\)

但是我们发现，其实我们可以找一条竖直方向的线从左侧扫到右侧，那么我们就不需要考虑那么多了，我们只需要知道当前段是否为1，等于是把矩形拆成很多很多段，然后分别进行查询

我们发现每次我们等于是在进行区间加减操作，这个就很明显了吧，用线段树维护，每次查一下整个区间上有多少个点的 \(val > 0\)，乘上横坐标长度即可

具体实现时，我们考虑用四元组 \(x_1,y_1,y_2,tag=1\) 和 \(x_2,y_1,y_2,tag=-1\) 来分别表示一个矩形的两个端点

我们进行离散化后直接用线段树维护线段长度

/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define int long long
#define rep(i, a, b) for (int i = (a); (i) <= (b); ++i)
#define per(i, a, b) for (int i = (a); (i) >= (b); --i)
#define whlie while
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> P;

namespace scan {
template <typename T>
inline void read(T& x) {
    x = 0;
    char c = getchar();
    int f = 0;
    for (; !isdigit(c); c = getchar())
        f |= (c == '-');
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ 48);
    if (f)
        x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x), read(args...);
}
template <typename T>
inline void write(T x, char ch) {
    if (x < 0)
        putchar('-'), x = -x;
    static short st[30], tp;
    do
        st[++tp] = x % 10, x /= 10;
    while (x);
    while (tp)
        putchar(st[tp--] | 48);
    putchar(ch);
}
template <typename T>
inline void write(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    static short st[30], tp;
    do
        st[++tp] = x % 10, x /= 10;
    while (x);
    while (tp)
        putchar(st[tp--] | 48);
}

inline void write(char ch) {
    putchar(ch);
}
}  // namespace scan
using namespace scan;
int n, m, tot;
int a1, a2, b1, b2, res;
int Y[N];
struct node {
    int l, r, x, mark;
    bool operator<(node line2) {
        return x < line2.x;
    }
} line[N];

inline int lc(int p) {
    return p << 1;
}
inline int rc(int p) {
    return p << 1 | 1;
}

struct node2 {
    int l, r, sum, tag;
} tr[N << 3];
inline void push_up(int p, int l, int r) {
    if (tr[p].tag)
        tr[p].sum = Y[r] - Y[l - 1];
    else
        tr[p].sum = tr[lc(p)].sum + tr[rc(p)].sum;
}

inline void update_tree(int p, int l, int r, int ql, int qr, int k) {
    if (ql > r || qr < l)
        return;
    if (ql <= l && r <= qr) {
        tr[p].tag += k;
        push_up(p, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update_tree(lc(p), l, mid, ql, qr, k);
    update_tree(rc(p), mid + 1, r, ql, qr, k);
    push_up(p, l, r);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    read(n);
    rep(i, 1, n) {
        read(a1, b1, a2, b2);
        line[i] = (node){b1, b2, a1, 1};
        line[i + n] = (node){b1, b2, a2, -1};
        Y[i] = b1;
        Y[i + n] = b2;
    }
    n <<= 1;
    sort(Y + 1, Y + 1 + n);
    tot = unique(Y + 1, Y + 1 + n) - (Y + 1);
    rep(i, 1, n) {
        line[i].l = lower_bound(Y + 1, Y + 1 + tot, line[i].l) - Y + 1;
        line[i].r = lower_bound(Y + 1, Y + 1 + tot, line[i].r) - Y;
    }
    sort(line + 1, line + 1 + n);
    rep(i, 1, n) {
        res += 1ll * tr[1].sum * (line[i].x - line[i - 1].x);
        update_tree(1, 1, tot, line[i].l, line[i].r, line[i].mark);
    }
    write(res, '\n');
    return 0;
}
// write:RevolutionBP

这篇关于扫描线的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！