全紫RE求调
查看原帖
全紫RE求调
365113
fly_x楼主2024/8/8 11:53
#include <bits/stdc++.h>
#define ls u * 2
#define rs u * 2 + 1
#define int long long
using namespace std;
struct tree{
	int sum, num, len;
	bool lf, rf;
} t[2000005];
struct edge{
	int l, r, h, f;
} e[2000005];
void pushup(int u, int l, int r){
	if (t[u].sum){
		t[u].num = 1;
		t[u].len = r-l+1;
		t[u].lf = t[u].rf = 1;
	} else if (l == r){
		t[u].sum = t[u].num = t[u].len = 0;
		t[u].lf = t[u].lf = 0;
	} else{
		t[u].num = t[ls].num + t[rs].num;
		if (t[ls].rf && t[rs].lf) t[u].num--;
		t[u].len = t[ls].len + t[rs].len;
		t[u].lf = t[ls].lf; t[u].rf = t[rs].rf;
	}
}
void add(int u, int l, int r, int L, int R, int k){
	if (L <= l && r <= R){
		t[u].sum += k;
		pushup(u, l ,r);
		return ;
	}
	int mid = (l + r) / 2;
	if (L <= mid) add(ls, l, mid, L, R, k);
	if (R > mid) add(rs, mid+1, r, L, R, k);
	pushup(u, l, r);
}
int n, x_1, y_1, x_2, y_2, cnt, ans;
int mx = 1<<62, mn = -mx, lst;
void add_edge(int l, int r, int h, int flg){
	e[++cnt].l = l, e[cnt].r = r;
	e[cnt].h = h, e[cnt].f = flg;
}
bool cmp(edge a, edge b){
	if (a.h == b.h) return a.f > b.f;
	return a.h < b.h;
}
main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lld%lld%lld%lld", &x_1, &y_1, &x_2, &y_2);
		mx = max(mx, max(x_1, x_2));
		mn = min(mn, min(x_1, x_2));
		add_edge(x_1, x_2, y_1,  1);
		add_edge(x_1, x_2, y_2, -1);
	}
	if (mn <= 0){
		for (int i = 1; i <= cnt; i++){
			e[i].l += -mn + 1;
			e[i].r += -mn + 1;
		}
		mx -= mn;
	}
	sort(e + 1, e + cnt + 1, cmp);
	for (int i = 1; i <= cnt; i++){
		add(1, 1, mx, e[i].l, e[i].r-1, e[i].f);
		while(e[i].h == e[i+1].h && e[i].f == e[i+1].f)
			++i, add(1, 1, mx, e[i].l, e[i].r-1, e[i].f);
		ans += t[1].len * (e[i+1].h - e[i].h);
	}
	printf("%lld", ans);
	return 0;
}

2024/8/8 11:53
加载中...