主要思路
这个题有点 nb。
按道理来讲直接做第二问得要 \(\Theta(n^4)\) 的时间，而且看上去也没有什么搞头。我们考虑处理出所有的接壤位置 \( (x, y, c_a, c_y) \) 代表颜色为 \(c_x\) 、编号 \(x\) 的点和颜色为 \(c_y\) 、编号 \(y\) 的点接壤。这样的接壤位置只有 \(\Theta(n^2)\) 个，所以我们分类出来之后再用并查集搞即可。
这个题有点 nb。
按道理来讲直接做第二问得要 \(\Theta(n^4)\) 的时间，而且看上去也没有什么搞头。我们考虑处理出所有的接壤位置 \( (x, y, c_a, c_y) \) 代表颜色为 \(c_x\) 、编号 \(x\) 的点和颜色为 \(c_y\) 、编号 \(y\) 的点接壤。这样的接壤位置只有 \(\Theta(n^2)\) 个，所以我们分类出来之后再用并查集搞即可。
kal0rona 越来越 sb了。
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。
这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。
考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。
这道题应该是并查集域的裸题，不讲。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= 2 * n; i++)
fa[i] = i;
while (m--)
{
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (opt == 0)
unite(x, y), unite(x + n, y + n);
else if (opt == 1 || opt == 2)
unite(x, y + n), unite(x + n, y);
else if (find(x) == find(y) || find(x + n) == find(y + n))
puts("1");
else
puts("0");
}
return 0;
}