CF793G Oleg and chess（线段树优化建图）

题目大意

有一个 \(n×n\) 的矩阵，每行每列至多能放一个棋子，另外有 \(q\) 个矩形的区域不能放棋子（这些矩形区域互不相交），问最多能放多少个棋子。\(n,q≤10^4\)

解题思路

做这题看不懂题解，想了简单的做法，但 3400 就这吗？结果写了一下就 A 了（

首先你需要会几个知识点即可：

1. 行列连边求最大匹配即为答案。
2. 会线段树优化建图
3. 会扫描线

首先选一个格子可以看做这个格子所在的行和列匹配，最多选出格子的数量就是最大匹配，也是网络流的最大流。

边数太多考虑线段树+扫描线优化建图，我们维护行中没有被矩形覆盖的点，这个就是扫描线的模板题了，不知道为什么这题要保证矩形不交，看起来即使相交也可以做的。

具体说一下吧，离线下来，将所有的矩形拆成两个边界，从左向右扫，扫到矩形的左边界则做线段覆盖，那么把线段树对应的节点置为 0 即可，扫到右边界就是线段删除，对应的节点新建一个点，向两个儿子连边即可。由于题目保证不相交，所以我们 build 的时候直接记录区域内无限制时的节点编号即可。

总时间复杂度 \(Flows(n\log n,n \log n)\) 没有其他题解里所带的 \(\Theta(n^2)\)

namespace Flows {
	const int M = 2005500;
	int cur[M], h[M], dep[M], ne[M], to[M], w[M], cnt, s, t, tot = 1;
	inline void add(int x, int y, int z) { ne[++tot] = h[x], to[h[x] = tot] = y, w[tot] = z; }
	inline void adde(int x, int y, int z) { add(x, y, z), add(y, x, 0); }
	int dfs(int x, int lim) {
		if (!lim || x == t) return lim;
		int res = 0, fl;
		for (int &i = cur[x], y; i; i = ne[i]) {
			if (dep[y = to[i]] != dep[x] + 1 || !w[i]) continue;
			fl = dfs(y, min(lim, w[i]));
			lim -= fl, res += fl;
			w[i] -= fl, w[i^1] += fl;
			if (!lim) return res;
		}
		return res;
	}
	queue<int> q;
	bool bfs(void) {
		memset(dep, 0, cnt * 4 + 20);
		dep[s] = 1, q.push(s);
		while (q.size()) {
			int x = q.front(); q.pop();
			for (int i = h[x], y; i; i = ne[i]) 
				if (!dep[y = to[i]] && w[i]) dep[y] = dep[x] + 1, q.push(y);
		}
		if (!dep[t]) return 0;
		memcpy(cur, h, cnt * 4 + 20);
		return 1;
	}
	int flow(void) {
		int ans = 0;
		while (bfs()) ans += dfs(s, 1e9);
		return ans;
	}
}
using Flows::cnt;
using Flows::adde;
using Flows::s;
using Flows::t;
using Flows::flow;

#define ls p << 1
#define rs ls | 1
const int hinf = 1e8;
const int N = 10500;
int id[N<<2], _1[N<<2], tag[N<<2], n, q;
void build(int p, int l, int r) {
	if (l == r) return adde(id[p] = _1[p] = l, t, 1);
	int mid = (l + r) >> 1; id[p] = _1[p] = ++cnt;
	build(ls, l, mid), build(rs, mid + 1, r);
	adde(_1[p], _1[ls], hinf), adde(_1[p], _1[rs], hinf);
}

void change(int p, int l, int r, int L, int R) {
	if (L <= l && r <= R) return tag[p] ^= 1, id[p] = tag[p] ? 0 : _1[p], void();
	int mid = (l + r) >> 1; id[p] = ++cnt;
	if (L <= mid) change(ls, l, mid, L, R);
	if (R > mid) change(rs, mid + 1, r, L, R);
	if (id[ls]) adde(id[p], id[ls], hinf);
	if (id[rs]) adde(id[p], id[rs], hinf);
}

vector<pair<int, int> > v1[N], v2[N];
int main() {
	read(n), read(q), s = cnt = n + 1, t = ++cnt;
	for (int i = 1, x1, x2, y1, y2;i <= q; ++i) {
		read(x1), read(y1), read(x2), read(y2);
		v1[x1].emplace_back(y1, y2), v2[x2 + 1].emplace_back(y1, y2);
	}
	build(1, 1, n);
	for (int i = 1;i <= n; ++i) {
		for (auto t: v2[i]) change(1, 1, n, t.fi, t.se);
		for (auto t: v1[i]) change(1, 1, n, t.fi, t.se);
		adde(s, id[1], 1);
	}
	write(flow());
	return 0;
}