改之前:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 100;
typedef long long ll;
int n, len;
struct node {int x1, x2, y, vis;} seg[N << 1];
int sum[N << 4], lazy[N << 4], b[N << 1];
ll ans;
int id (int x) {return lower_bound (b + 1, b + len + 1, x) - b;}
bool cmp (const node &x, const node &y) {return x.y < y.y;}
inline int ls (int p) {return p >> 1;}
inline int rs (int p) {return p >> 1 | 1;}
void push_up (int p, int l, int r) {
if (lazy[p] > 0) sum[p] = b[r + 1] - b[l];
else sum[p] = sum[ls(p)] + sum[rs(p)];
}
void update (int p, int l, int r, int nl, int nr, int f) {
if (nl <= l && r <= nr) {
lazy[p] += f;
push_up(p, l, r);
return ;
}
int mid = l + r >> 1;
if (nl <= mid) update (ls(p), l, mid, nl, nr, f);
if (mid < nr) update (rs(p), mid + 1, r, nl, nr, f);
push_up(p, l, r);
}
void dfs (int p) {
if (p > 6) return ;
cout << p << " " <<sum[p] << " " << lazy[p] << '\n';
dfs(ls(p)), dfs(rs(p));
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1, X1, Y1, X2, Y2; i <= n; i ++ ) {
cin >> X1 >> Y1 >> X2 >> Y2;
seg[i * 2 - 1] = {X1, X2, Y1, 1};
seg[i * 2] = {X1, X2, Y2, -1};
b[i * 2 - 1] = X1, b[i * 2] = X2;
}
sort (b + 1, b + n * 2 + 1);
sort (seg + 1, seg + n * 2 + 1, cmp);
len = unique(b + 1, b + n * 2 + 1) - b - 1;
for (int i = 1; i < 2 * n; i ++ ) {
update (1, 1, len - 1, id(seg[i].x1), id(seg[i].x2) - 1, seg[i].vis);
ans += sum[1] * 1ll * (seg[i + 1].y - seg[i].y);
}
cout << ans << '\n';
return 0;
}
改之后:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 100;
typedef long long ll;
int n, len;
struct node {int x1, x2, y, vis;} seg[N << 1];
int sum[N << 4], lazy[N << 4], b[N << 1];
ll ans;
int id (int x) {return lower_bound (b + 1, b + len + 1, x) - b;}
bool cmp (const node &x, const node &y) {return x.y < y.y;}
inline int ls (int p) {return p << 1;}
inline int rs (int p) {return p << 1 | 1;}
void push_up (int p, int l, int r) {
if (lazy[p] > 0) sum[p] = b[r + 1] - b[l];
else sum[p] = sum[ls(p)] + sum[rs(p)];
}
void update (int p, int l, int r, int nl, int nr, int f) {
if (nl <= l && r <= nr) {
lazy[p] += f;
push_up(p, l, r);
return ;
}
int mid = l + r >> 1;
if (nl <= mid) update (ls(p), l, mid, nl, nr, f);
if (mid < nr) update (rs(p), mid + 1, r, nl, nr, f);
push_up(p, l, r);
}
void dfs (int p) {
if (p > 6) return ;
cout << p << " " <<sum[p] << " " << lazy[p] << '\n';
dfs(ls(p)), dfs(rs(p));
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1, X1, Y1, X2, Y2; i <= n; i ++ ) {
cin >> X1 >> Y1 >> X2 >> Y2;
seg[i * 2 - 1] = {X1, X2, Y1, 1};
seg[i * 2] = {X1, X2, Y2, -1};
b[i * 2 - 1] = X1, b[i * 2] = X2;
}
sort (b + 1, b + n * 2 + 1);
sort (seg + 1, seg + n * 2 + 1, cmp);
len = unique(b + 1, b + n * 2 + 1) - b - 1;
for (int i = 1; i < 2 * n; i ++ ) {
update (1, 1, len - 1, id(seg[i].x1), id(seg[i].x2) - 1, seg[i].vis);
ans += sum[1] * 1ll * (seg[i + 1].y - seg[i].y);
}
cout << ans << '\n';
return 0;
}
没错,ls() 和 rs() 左移右移方向写错了(错过不止一次了已经)
大家一定要引以为戒(qwq)