题目描述：
有区间 $[1,\cdots,n]$，有三种操作：
- 操作一：给出 $x,y$，合并为一个节点
- 操作二：给出 $x,y$，合并区间 $[x,y]$ 为一个节点
- 操作三：给出 $x,y$ 判断 $x,y$ 是否在一个节点。
数据范围：
$1\le n\le 2\times 10^5, 1\le q\le 5\times 10^5$
题解：
需要使用并查集维护一段连续的数字。
可以使用一个 $next[i]$ 数组表示每个元素的下一个未被合并的元素，也就是下一段区间的起点。初始值 $next[i] = i + 1$，表示每个元素的下一个区间起点就是 $i + 1$。相当于把整个连续区间当成了一个点，然后合并时就可以直接unite。
操作一：直接使用并查集unite(x, y)。
操作二：从 $x$ 开始，每次先找到 $x$ 的父亲节点 $xp$，然后合并 $xp,yp$。同时修改 $xp$ 的 $next$。将 $next[xp]$ 修改为 $next[y]$。
操作三：直接用并查集判断 $xp$ 是否等于 $yp$。
再比如订单编号。
第一个编号是正常的，后面的编号都要找到大于等于前一个，并且没有出现过的最小的数字。可以每次合并 $x,x + 1$，这样的话每次 $find$ 就可以找到正确答案。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int fa[maxn], nex[maxn];
void init()
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
nex[i] = i + 1;
}
}
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
void unite(int u, int v)
{
int up = find(u);
int vp = find(v);
if (up == vp)
return;
fa[up] = vp;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int q;
read(n, q);
int type, x, y;
init();
for (int i = 1; i <= q; ++i)
{
read(type, x, y);
if (type == 1)
{
unite(x, y);
}
else if (type == 2)
{
int cur = x;
int yp = find(y);
while (cur <= y)
{
unite(cur, yp);
int tmp = cur;
cur = nex[cur];
nex[tmp] = nex[y];
}
}
else
{
cout << (find(x) == find(y) ? "YES" : "NO") << endl;
}
}
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 5e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
unordered_map<int, int> fa;
int find(int u)
{
if (!fa.count(u))
{
fa[u] = u;
return u;
}
if (fa[u] == u)
return u;
return fa[u] = find(fa[u]);
}
void unite(int u, int v)
{
int up = find(u);
int vp = find(v);
if (up == vp)
return;
if (vp < up)
swap(up, vp);
fa[up] = vp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int x;
for (int i = 0; i < n; ++i)
{
cin >> x;
x = find(x);
cout << x << " ";
unite(x, x + 1);
}
cout << endl;
return 0;
}
|