扫描线板子题，题目在洛谷 P5490 【模板】扫描线
样例都没过，提交全RE，求大佬帮忙
洛谷提交记录：
\displaystyle{^{\color{orange}\sf \large {SunSkydp}}_{\color{grey}\sf 2022.08.15}\ \ ^{\sf \colorbox{red}{Unaccepted}}_{\color{#red}\sf \large 0}\ \sf \ \ \ \color{blue} P5490 【模板】扫描线\ \ \ \ \color{grey}0ms/0B/2.60KB\ C^{_{_{++}}}14(GCC9) O2}
这组数据可过:
输入
2
1 2 4 3
2 1 4 3
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
const int N = 1600005;
vector<int> xx;
vector<array<int, 4>> line;
struct MIN{
int minv, mincnt;
};
MIN operator + (const MIN &l, const MIN &r) {
MIN a;
a.minv = min(l.minv, r.minv);
if(l.minv == r.minv) a.mincnt = l.mincnt + r.mincnt;
else if(l.minv < r.minv) a.mincnt = l.mincnt;
else a.mincnt = r.mincnt;
return a;
}
struct node {
int t;
MIN val;
} seg[N * 8];
void update(int id) {
seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}
void tag(int id, int t) {
seg[id].val.minv = seg[id].val.minv + t;
seg[id].t = seg[id].t + t;
}
void pushdown(int id) {
if(seg[id].t != 0) {
seg[id * 2].val.minv = seg[id * 2].val.minv + seg[id].t;
seg[id * 2].t = seg[id * 2].t + seg[id].t;
seg[id * 2 + 1].val.minv = seg[id * 2 + 1].val.minv + seg[id].t;
seg[id * 2 + 1].t = seg[id * 2 + 1].t + seg[id].t;
//tag(id * 2, seg[id].t);
//tag(id * 2 + 1, seg[id].t);
seg[id].t = 0;
}
}
void build(int id, int l, int r) {
if(l == r) {
seg[id].val = {0, xx[r] - xx[r - 1]};
} else {
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
}
void modify(int id, int l, int r, int x, int y, int t) {
if(l == x && y == r) {
seg[id].val.minv = seg[id].val.minv + t;
seg[id].t = seg[id].t + t;
return ;
}
int mid = (l + r) / 2;
pushdown(id);
if(x <= mid) modify(id * 2, l, mid, x, y, t);
else if(y > mid) modify(id * 2 + 1, mid + 1, r, x, y, t);
else {
modify(id * 2, l, mid, x, mid, t);
modify(id * 2 + 1, mid + 1, r, mid + 1, y, t);
}
update(id);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
int x1, x2, yy1, yy2;
scanf("%d%d%d%d", &x1, &yy1, &x2, &yy2);
xx.push_back(x1);
xx.push_back(x2);
line.push_back({yy1, 1, x1, x2});
line.push_back({yy2, -1, x1, x2});
}
sort(line.begin(), line.end());
sort(xx.begin(), xx.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
m = xx.size() - 1;
build(1, 1, m);
int lasty = 0;
int sumlen = seg[1].val.mincnt;
ll ans = 0;
for(auto lne : line) {
int coverS = sumlen;
if(seg[1].val.minv == 0) coverS = sumlen - seg[1].val.mincnt;
ans += (ll) (lne[0] - lasty) * coverS;
lasty = lne[0];
int x1 = lower_bound(xx.begin(), xx.end(), lne[2]) - xx.begin() + 1;
int x2 = lower_bound(xx.begin(), xx.end(), lne[3]) - xx.begin();
if(x1 > x2) continue;
modify(1, 1, m, x1, x2, lne[1]);
}
printf("%lld\n", ans);
return 0;
}