[AtCoder] [經典競程 90 題] 012 - Red Painting（★4）

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_l
題目大意:
給定一個 $N \times M$ 的網格上，現在有兩種可能的操作，其中一種 1 x y 代表把 ($x$, $y$) 塗成紅色的；另外一種 2 p q r s 代表詢問 ($p$, $q$) 可否只透過紅色的格子上下左右移動到 ($r$, $s$)。

---

詢問的時候等價問兩個點是不是在同個連通塊裡，所以弄個併查集每次塗色的時候都更新一下當前的連通資訊就好了。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;

class DSU {
private:
	vector<int> p;
public:
	void init(int n) {
		p.resize(n);
		iota(p.begin(), p.end(), 0);
	}
	int query(int x) {
		if (p[x] != x) p[x] = query(p[x]);
		return p[x];
	}
	void merge(int x, int y) {
		p[query(x)] = query(y);
	}
} dsu;

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool a[N][N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	dsu.init(n * m);
	auto Idx = [&m](int i, int j){
		return i * m + j;
	};
	int q; cin >> q;
	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			int x, y; cin >> x >> y;
			a[--x][--y] = true;
			for (int dt = 0; dt < 4; ++dt) {
				int nx = x + dx[dt], ny = y + dy[dt];
				if (0 > nx or nx >= n) continue;
				if (0 > ny or ny >= m) continue;
				if (a[nx][ny]) dsu.merge(Idx(x, y), Idx(nx, ny));
			}
		} else {
			int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
			--x1, --y1, --x2, --y2;
			cout << ((a[x1][y1] and a[x2][y2] and dsu.query(Idx(x1, y1)) == dsu.query(Idx(x2, y2))) ? "Yes" : "No") << '\n';
		}
	}
	return 0;
}