社区讨论

代码目测无误,与题解自行对了一下,没有查出错误,求帮忙

P5490【模板】扫描线 & 矩形面积并参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo1povgu
此快照首次捕获于
2023/10/23 00:57
2 年前
此快照最后确认于
2023/11/03 01:37
2 年前
查看原帖
https://www.luogu.com.cn/blog/478585/qian-tan-sao-miao-xian
代码类似上面写的
CPP
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

const int N = 2e5 + 50;
const int M = 1e5 + 50;
const int Mod = 1e9 + 7;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

int n, m;

struct node
{
    int x, y, y_, k;
} a[N << 1];

int b[N << 1];

map<int, int> pos;

bool cmp(node x, node y)
{
    return x.x < y.x;
}

int L[N << 2], R[N << 2], Sum[N << 2], Lazy[N << 2];

int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void push_up(int p)
{
    if (Lazy[p])
        Sum[p] = b[R[p] + 1] - b[L[p]];
    else
        Sum[p] = Sum[ls(p)] + Sum[rs(p)];
}

void build(int p, int l, int r)
{
    L[p] = l, R[p] = r;
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
}

void update(int p, int l, int r, int k)
{
    if (r < L[p] || l > R[p])
        return;
    if (l <= L[p] && R[p] <= r)
        Lazy[p] += k;
    else
    {
        update(ls(p), l, r, k);
        update(rs(p), l, r, k);
    }
    push_up(p);
}

signed main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        int x = read(), y = read(), x_ = read(), y_ = read();
        a[i] = (node){x, y, y_, 1};
        a[i + n] = (node){x_, y, y_, -1};
        b[++m] = y, b[++m] = y_;
    }
    n <<= 1;
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    for (int i = 1; i <= m; ++i)
        pos[b[i]] = i;
    build(1, 1, n);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        update(1, pos[a[i].y], pos[a[i].y_] - 1, a[i].k);
        ans = ans + Sum[1] * (a[i + 1].x - a[i].x);
    }
    printf("%lld\n", ans);
    return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...