题目大意
起初,数字 1∼n1\sim n1∼n 之间相互独立,给出 qqq 次查询,每次查询为以下三种的一种:
* 将两个没有连接起来的数字按顺序前后连接起来;
* 将两个已经连接起来的数字分开;
* 输出某一个数字所有链上从头到尾所有的数字以及个数。
解题思路
由于要涉及到按顺序连接和断开的操作,不难想到我们可以通过使用数组模拟链表的方式进行这一系列操作。
lil_ili :表示 iii 这个数字左边的数字是多少,如果没有则为 000 。
rir_iri :表示 iii 这个数字右边的数字是多少,如果没有则为 000 。
于是,对于第一种操作 1 x y ,我们可以用以下代码完成:
注意这里是有顺序的,所以 xxx 和 yyy 的顺序不能反。
对于第二种操作 2 x y ,我们可以用以下代码完成:
对于第三种操作,我们可以直接先暴力找到 xxx 所在链的最左侧点,然后再依次向后遍历,存储所有的数,最后输出其个数以及所有数字即可。
参考代码