扫描线求面积并板子求调
  • 板块灌水区
  • 楼主hjqhs
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/8 21:38
  • 上次更新2024/8/9 19:50:07
查看原帖
扫描线求面积并板子求调
724988
hjqhs楼主2024/8/8 21:38
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000005;
const int INF = 0x3f3f3f3f;
int n, ans, X[N << 1];
struct scanlinee{ int l, r, h, mark; } linee[N << 1];
bool cmp(scanlinee a, scanlinee b) { return a.h < b.h; }
struct sgt{ int l, r, cnt, len; } t[N << 2];
int ls(int rt) { return rt << 1; }
int rs(int rt) { return rt << 1 | 1; }
void build(int rt, int l, int r) {
	// cout << "build";
	t[rt].l = l, t[rt].r = r;
	t[rt].cnt = t[rt].len = 0;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(ls(rt), l, mid);
	build(rs(rt), mid + 1, r);	
}
void pushup(int rt){
	// cout << "pushup";
	if(t[rt].cnt) t[rt].len = X[t[rt].r + 1] - X[t[rt].l];
	else t[rt].len = t[ls(rt)].len + t[rs(rt)].len;
}
void update(int updl, int updr, int rt, int v) {
	if(X[t[rt].r] + 1 <= updl; && updr <= X[t[rt].l]) return;
	// cout << "update";
	if(updl <= X[t[rt].l] && X[t[rt].r + 1] <= updr) return t[rt].cnt += v, void();
	update(updl, updr, ls(rt), v);
	update(updl, updr, rs(rt), v);
	pushup(rt);	
}
void solve() {
	cin >> n;
	// cout << clock() - now << '\n';
	rep(i, 1, n) {
		int X1, Y1, X2, Y2; cin >> X1 >> Y1 >> X2 >> Y2;
		X[(i << 1) - 1] = X1, X[i << 1] = X2;
		linee[(i << 1) - 1] = (scanlinee) {X1, X2, Y1, 1};
		linee[(i << 1)] = (scanlinee) {X1, X2, Y2, -1};
	}
	n <<= 1;
	sort(linee + 1, linee + 1 + n, cmp), sort(X + 1, X + 1 + n);
	int tot = unique(X + 1, X + 1 + n) - X - 1;
	build(1, 1, tot - 1); 
	rep(i, 1, n - 1) {
		// update(linee[i].l, linee[i].r, 1, linee[i].mark);
		ans += t[i].len * (linee[i + 1].h - linee[i].h);
	}
	cout << ans;
	return;
}
signed main() {
	// int noww = clock();
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	// cin >> T;
	while(T --) solve();
	return 0;
}
2024/8/8 21:38
加载中...