526互联

扫描线

发布时间 2023-12-01 16:36:12作者: value0

扫描线

应用：一般用于计算多个矩形的总面积(重叠算一次)、总周长、最大重叠区域权值等问题。

总结：

  1. 运用线段树来实现。
  2. 计算多个矩形的总面积(重叠算一次)，虽然是区间修改，但是由于我们不用更新到子树上，所以不需要\(pushdown\).
  3. 最大重叠区域权值问题，一般需要需要基本转化，比如从二维数点问题转移过来。
  4. 计算总周长没看。。。
  5. 此处暂且仅用来记录，具体思路不错阐述，已经有很多题解，可自行学习（复习）。

例题:

P5490 【模板】扫描线

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
using i128 = __int128_t;
int n, w, h;
const int N = 1E5 + 10;
int cnt = 0;
vector<int> ys;
struct segment
{
    int x, y1, y2, v;
    bool operator<(segment t)
    {
        return x < t.x;
    }
} seg[2 * N];

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

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 = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else
    {
        tr[u].len = 0;
    }
}

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

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

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        ys.push_back(y1);
        ys.push_back(y2);
        seg[cnt++] = {x1, y1, y2, 1};
        seg[cnt++] = {x2, y1, y2, -1};
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    auto find = [&](int x)
    {
        return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
    };
    build(1, 0, ys.size() - 2);
    sort(seg, seg + n * 2);
    ll res = 0;
    for (int i = 0; i < 2 * n; i++)
    {
        if (i)
        {
            res += (ll)tr[1].len * (seg[i].x - seg[i - 1].x);
        }
        modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].v);
    }
    cout << res << endl;
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

P1502 窗口的星星

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
using i128 = __int128_t;
int n, w, h;
const int N = 1E5 + 10;
int cnt = 0;
vector<int> ys;
struct segment
{
    ll x, y1, y2, v;
    bool operator<(segment t)
    {
        if (x != t.x)
        {
            return x < t.x;
        }
        return v < t.v;
    }
} seg[2 * N];

struct node
{
    ll l, r;
    ll val = 0;
    ll add = 0;
} tr[8 * N];

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

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

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

void modify(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add += v;
        tr[u].val += v;
        // cout << tr[u].val << endl;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
    {
        modify(u << 1, l, r, v);
    }
    if (r > mid)
    {
        modify(u << 1 | 1, l, r, v);
    }
    pushup(u);
}

void solve()
{
    ys.clear();
    cin >> n >> w >> h;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        ll x, y, v;
        scanf("%lld %lld %lld", &x, &y, &v);
        seg[cnt++] = {x, y, y + h, v};
        seg[cnt++] = {x + w, y, y + h, -v};
        ys.push_back(y);
        ys.push_back(y + h);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    build(1, 0, ys.size() - 2);
    auto find = [&](ll x)
    {
        return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
    };
    sort(seg, seg + 2 * n);
    ll ans = 0;
    // cout << seg[2].y1 << endl;
    for (int i = 0; i < 2 * n; i++)
    {
        if (i)
        {
            ans = max(ans, (ll)tr[1].val);
        }
        modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].v);
        // cout << i << ' ' << ans << endl;
        // cout << seg[i].x <<' ' << seg[i].y1 << ' ' << seg[i].y2 << ' ' << seg[i].v << endl;
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

ABC 327 F - Apples

和上题一样。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
using i128 = __int128_t;
int n, w, h;
const int N = 2E5 + 10;
int cnt = 0;
vector<int> ys;
struct segment
{
    ll x, y1, y2, v;
    bool operator<(segment t)
    {
        if (x != t.x)
        {
            return x < t.x;
        }
        return v < t.v;
    }
} seg[2 * N];

struct node
{
    ll l, r;
    ll val = 0;
    ll add = 0;
} tr[8 * N];

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

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

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

void modify(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add += v;
        tr[u].val += v;
        // cout << tr[u].val << endl;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
    {
        modify(u << 1, l, r, v);
    }
    if (r > mid)
    {
        modify(u << 1 | 1, l, r, v);
    }
    pushup(u);
}

void solve()
{
    ys.clear();
    cin >> n >> w >> h;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        ll x, y, v;
        scanf("%lld %lld", &x, &y);
        seg[cnt++] = {x, y, y + h, 1};
        seg[cnt++] = {x + w, y, y + h, -1};
        ys.push_back(y);
        ys.push_back(y + h);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    build(1, 0, ys.size() - 2);
    auto find = [&](ll x)
    {
        return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
    };
    sort(seg, seg + 2 * n);
    ll ans = 0;
    // cout << seg[2].y1 << endl;
    for (int i = 0; i < 2 * n; i++)
    {
        if (i)
        {
            ans = max(ans, (ll)tr[1].val);
        }
        modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].v);
        // cout << i << ' ' << ans << endl;
        // cout << seg[i].x <<' ' << seg[i].y1 << ' ' << seg[i].y2 << ' ' << seg[i].v << endl;
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}