ACM模版
描述
题解
典型的并查集问题，由于需要区间更新，所以这里要维护一个
pre[]
数组，表示当前记录点与在它前边且最靠近它的不同部门的点。
代码十分容易理解，就不再赘述了。
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN =
2e5 +
10;
int n, q;
int fat[MAXN];
int pre[MAXN];
int find(
int x)
{
return x == fat[x] ? x : fat[x] = find(fat[x]);
}
void merge_1(
int x,
int y)
{
x = find(x);
y = find(y);
if (x != y)
{
fat[y] = x;
}
}
void merge_2(
int x,
int y)
{
for (
int i = y, p; i >= x && pre[i] >= x; i = p)
{
p = pre[i];
fat[find(p)] = fat[find(i)];
pre[i] = pre[p];
}
}
template <
class T>
inline void scan_d(T &ret)
{
char c;
ret =
0;
while ((c = getchar()) <
'0' || c >
'9');
while (c >=
'0' && c <=
'9')
{
ret = ret *
10 + (c -
'0'), c = getchar();
}
}
void init()
{
for (
int i =
1; i <= n; ++i)
{
fat[i] = i;
pre[i] = i -
1;
}
}
int main()
{
scan_d(n), scan_d(q);
init();
int t, x, y;
while (q--)
{
scan_d(t), scan_d(x), scan_d(y);
if (t ==
1)
{
merge_1(x, y);
}
else if (t ==
2)
{
merge_2(x, y);
}
else
{
if (find(x) == find(y))
{
puts(
"YES");
}
else
{
puts(
"NO");
}
}
}
return 0;
}
