《技术》学考及选考相关问题请联系张博士13958083702(手机和微信同号) 问题 5690 --☀阳☀光☀开☀朗☀并☀查☀集☀

5690: ☀阳☀光☀开☀朗☀并☀查☀集☀

时间限制: 2 Sec  内存限制: 256 MB
提交: 52  解决: 12
[提交][状态][命题人:]

题目描述

最后所有人目光移向这题问这题涉及的算法是什么
我看看这题说算法是
☀阳☀光☀开☀朗☀并☀查☀集☀
☀阳☀光☀开☀朗☀并☀查☀集☀

有 n 个学生在学校里,学生编号从 1 到 n 。一开始每个人都是一对一教学,每个人都在一个班级里,每个班级里只有一个人,共有 n 个班级。

接下来,有 q 次班级操作,每次操作为以下三种之一:
1. 将 x 同学所在的班级与 y 同学所在的班级合并。(1≤x,y≤n)
2. 将 x 同学所在的班级、 x+1 同学所在的班级、 x+2 同学所在的班级、... 、 y 同学所在的班级合并在一起。 (1≤x≤y≤n)
3. 查询 x 同学与 y 同学是否在同个班级内。(1≤x,y≤n)

输入

第一行包含两个正整数 n,q (1≤n≤2*10^5, 1≤q≤5*10^5) ,表示学生数和操作数。
接下来 q 行,每行包含三个整数 op,x,y (op∈{1,2,3}, 1≤x,y≤n) ,表示操作种类,和参数 x,y 。

输出

对于每个操作3,输出一行。
若 x 同学与 y 同学在同个班级内,则输出 "YES" ,否则输出 "NO" 。
样例输入
Copy
8 6
3 2 5
1 2 5
3 2 5
2 4 7
2 1 2
3 1 7
样例输出
Copy
NO
YES
YES

提示

来源

[提交][状态]

如有问题,请咨询客服
浙ICP备20001167号