社区讨论
代码目测无误,与题解自行对了一下,没有查出错误,求帮忙
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 条回复,欢迎继续交流。
正在加载回复...