如题,本地运行可以,在 luoguide 上测样例就会 RE,不知道为什么,求助 qwq
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5000 * 2;
struct seg {
int x, yy1, yy2, tp;
} Q[N + 10];
bool cmp(seg &x, seg &y) {
if(x.x != y.x) return x.x < y.x;
else x.tp > y.tp;
}
int pos[N + 10], ptot = 0;
int add[N * 4 + 10], sum[N * 4 + 10];
int ls(int x) {
return 2 * x;
}
int rs(int x) {
return 2 * x + 1;
}
void push_tag(int now, int s, int t, int v) {
add[now] += v;
if(add[now]) sum[now] = pos[t + 1] - pos[s];
else sum[now] = sum[ls(now)] + sum[rs(now)];
}
void push_up(int now, int s, int t) {
if(add[now]) sum[now] = pos[t + 1] - pos[s];
else sum[now] = sum[ls(now)] + sum[rs(now)];
}
void upd(int ql, int qr, int s, int t, int now, int v) {
if(ql <= s && t <= qr) {
push_tag(now, s, t, v);
return ;
}
int mid = (s + t) >> 1;
if(ql <= mid) upd(ql, qr, s, mid, ls(now), v);
if(qr > mid) upd(ql, qr, mid + 1, t, rs(now), v);
push_up(now, s, t);
}
int n, xx1[N + 10], yy1[N + 10], xx2[N + 10], yy2[N + 10];
int ans = 0;
void org() {
ptot = 0;
memset(add, 0, sizeof(add));
memset(sum, 0, sizeof(sum));
memset(pos, 0, sizeof(pos));
}
void forx() {
org();
for(int i = 1; i <= n; i++) {
Q[i * 2 - 1] = (seg){xx1[i], yy1[i], yy2[i], 1};
Q[i * 2] = (seg){xx2[i], yy1[i], yy2[i], -1};
pos[++ptot] = yy1[i];
pos[++ptot] = yy2[i];
}
}
void fory() {
org();
for(int i = 1; i <= n; i++) {
Q[i * 2 - 1] = (seg){yy1[i], xx1[i], xx2[i], 1};
Q[i * 2] = (seg){yy2[i], xx1[i], xx2[i], -1};
pos[++ptot] = xx1[i];
pos[++ptot] = xx2[i];
}
}
void work() {
sort(pos + 1, pos + ptot + 1);
int len = unique(pos + 1, pos + ptot + 1) - pos - 1;
for(int i = 1; i <= 2 * n; i++) {
Q[i].yy1 = lower_bound(pos + 1, pos + len + 1, Q[i].yy1) - pos;
Q[i].yy2 = lower_bound(pos + 1, pos + len + 1, Q[i].yy2) - pos;
}
sort(Q + 1, Q + 2 * n + 1, cmp);
upd(Q[1].yy1, Q[1].yy2 - 1, 1, len, 1, Q[1].tp);
int last = sum[1];
ans += last;
for(int i = 2; i <= 2 * n; i++) {
upd(Q[i].yy1, Q[i].yy2 - 1, 1, len, 1, Q[i].tp);
ans += abs(sum[1] - last);
last = sum[1];
}
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> xx1[i] >> yy1[i] >> xx2[i] >> yy2[i];
forx(), work();
fory(), work();
cout << ans << endl;
}