线段树之扫描线浅谈

#include <iostream>
#include <cstdio>
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1e4;
set< int > si;
vector< int > vi;
unordered_map< int, int > uti;
struct node {
	int l, r, y, flag;
	friend bool operator<(const node &a, const node &b) {
		return a.y < b.y;
	}
} sline[maxn << 1u];

inline void discrete() {
	vi.resize(si.size() + 1);
	int i = 0;
	for (const auto &x : si) {
		uti[x] = ++i;
		vi[i] = x;
	}
}

class SegTree {
	struct node {
		int l, r;
		int v, cnt;
	} tr[maxn << 1u << 2u];
	void pushup(int u) { tr[u].v = tr[u << 1u].v + tr[u << 1u | 1u].v; }
	void build(int u, int l, int r) {
		tr[u] = {l, r};
		if (l == r - 1) return;
		build(u << 1u, l, (l + r) >> 1u);
		build(u << 1u | 1u, (l + r) >> 1u, r);
	}
	void modify(int u, int l, int r, int flag) {
		if (tr[u].l >= r || tr[u].r <= l) return;
		if (tr[u].l >= l && tr[u].r <= r) {
			tr[u].cnt += flag;
			if (tr[u].cnt) tr[u].v = vi[tr[u].r] - vi[tr[u].l];
			else pushup(u);
		} else {
			modify(u << 1u, l, r, flag);
			modify(u << 1u | 1u, l, r, flag);
			if (!tr[u].cnt) pushup(u);
		}
	}
public:
	void init(const int n) { build(1, 1, n + 1); }
	int solve(int l, int r, int flag) {
		modify(1, l, r, flag);
		return tr[1].v;
	}
} st;

int main() {
	ios::sync_with_stdio(false);

	int n {};
	cin >> n;
	for (int i = 0; i < n; i++) {
		static int l, r, u, d;
		cin >> l >> u >> r >> d;
		si.insert(l), si.insert(r);
		sline[i << 1u] = {l, r, u, 1};
		sline[i << 1u | 1u] = {l, r, d, -1};
	}
	discrete();
	sort(sline, sline + (n << 1u));
	st.init(si.size() - 1);
	int ret = 0;
	for (int i = 0, len = (n << 1u) - 1; i < len; i++) {
		ret += st.solve(uti[sline[i].l], uti[sline[i].r], sline[i].flag)
			   * (sline[i + 1].y - sline[i].y);
	}
	printf("%d\n", ret);

	return 0;
}