萌新袜子求助,扫描线 20 pts。
查看原帖
萌新袜子求助,扫描线 20 pts。
677831
srds_cbddl楼主2023/8/23 20:16
// 答辩 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
struct scanning {
	ll lx, rx, y;
	int s;
	scanning () {};
	scanning (ll lx_, ll rx_, ll y_, int s_) {
		lx = lx_, rx = rx_, y = y_, s = s_;
	}
	bool operator < (const scanning &rhs) const {
		return y < rhs.y;
	}
} line[N << 1];
int n, len, flag[N << 2];
ll X[N << 1], sum[N << 2], ans;

inline void pushup(int u, int l, int r) {
	if (flag[u])
		sum[u] = X[r + 1] - X[l];
	else if (l == r)
		sum[u] = 0;
	else
		sum[u] = sum[u * 2] + sum[u * 2 + 1];
}

void update(int u, int l, int r, int tl, int tr, int c) {
	if (tl <= l && tr >= r) {
		flag[u] += c;
		pushup(u, l, r);
		return ;
	}
	int mid = (l + r) / 2;
	if (tr <= mid)
		update(u * 2, l, mid, tl, tr, c);
	else if (tl > mid)
		update(u * 2 + 1, mid + 1, r, tl, tr, c);
	else {
		update(u * 2, l, mid, tl, mid, c);
		update(u * 2 + 1, mid + 1, r, mid + 1, tr, c);
	}
	pushup(u, l, r);
}

int main() {
    cin >> n;
	for (int i = 1; i <= n; i ++) {
		double x, y, xx, yy;
		cin >> x >> y >> xx >> yy;
		line[++ len] = scanning(x, xx, y, 1), X[len] = x;
		line[++ len] = scanning(x, xx, yy, -1), X[len] = xx;
	}

	sort(X + 1, X + len + 1);
	sort(line + 1, line + len + 1);
	int k = unique(X + 1, X + len + 1) - X - 1;

	for (int i = 1; i < len; i ++) {
		int l = lower_bound(X, X + len + 1, line[i].lx) - X;
		int r = lower_bound(X, X + len + 1, line[i].rx) - X - 1;
		update(1, 1, k, l, r, line[i].s);
		ans += sum[1] * (line[i + 1].y - line[i].y);
	}

	cout << ans;
	return 0;
}
2023/8/23 20:16
加载中...