纸人(e)

输入文件名 e.in

输出文件名 e.out

题目描述

---

Jimmy 是一个酷爱玩游戏的人。一天，他闲着无聊，于是和 HXG 玩游戏。Jimmy 找到了一些小纸人，它们散布在地上。于是 HXG 就很无聊地给它们分别标上不同的 $1 \sim n$ 的编号。

Jimmy 会下一些指令，用绳子把某个纸人绑到某个纸人后面形成队列。指令的格式是 C x y，表示将编号为 $x$ 的纸人所在的队列接到编号为 $y$ 的纸人所在的队列后面。

HXG 会点燃 Jimmy 的纸人，格式为 F x，表示将编号为 $x$ 的纸人点燃。由于当时刮着强烈的东风，纸人着火后，只会顺着绳子点燃它后面连接的所有的纸人，而不会波及到它其它的纸人。纸人（包括绳子）着火后，会迅速被烧掉，到下一次操作时就烧完了，不留一点痕迹。

当然，由于纸人很多，密密麻麻地排列，HXG 不能清楚地看到当前的情形。所以他会发布指令，让小弟 hxg 去回答他的问题。指令的格式是 Q x，询问第 $x$个纸人的情况，hxg 要告诉 HXG 那个纸人所在队列最前面的那个纸人的编号和最后面的那个纸人的编号。如果第 $x$ 个纸人被烧掉了，就告诉 -1。

但是 hxg 的密集恐惧症犯了，所以这个艰巨的任务就交给你了！

输入

---

从文件 e.in 中读入数据。

第一行有两个整数 n 和 m，表示纸人的数量和双方一共发布的指令数量。 接下来 m 行，每行一条指令，定义请看【题目描述】。

输出

---

输出到文件 e.out 中。

回答 HXG 的每一个询问指令（输出被询问纸人所在队列最前面的那个纸人的编号和最后面的那个纸人的编号或 -1）。

样例数据

---

输入 #1

5 9
C 1 2
C 2 3
Q 2
C 4 5
Q 4
F 2
Q 3
C 4 3
Q 3

输出 #1

3 1
5 4
3 3
3 4

数据范围限制

---

对于 $30\%$ 的数据，$1 \le n \le 20,1 \le m \le 50$。
对于 $50\%$ 的数据，$1 \le n \le 500,1 \le m \le 2000$。
对于 $70\%$ 的数据，$1 \le n \le 100000,1 \le m \le 200000$。
对于 $100\%$ 的数据，$1 \le n \le 500000,1 \le m \le 500000$。
其中有 $30\%$ 的数据保证没有烧的操作。

提示

---

由于 Jimmy 被 HXG 搅得心烦意乱，可能会发布把被烧掉的纸人的所在队列与别的纸人合并，或是把在同一队列内纸人合并的指令。HXG 也可能会发布烧掉已经被烧掉的纸人的指令。这些指令是不合法的，直接跳过即可。

My Code

// 纸人(e)
#include <cstdio>
#include <iostream>
#define N 500005
using namespace std;
char ch;
bool Mp[N];
int n, m, x, y;
int d1[N], d2[N];
void init_set ();
int find_set_front (int);
int find_set_back (int);
void fire (int);
int main() {
	freopen ("e.in", "r", stdin);
	freopen ("e.out", "w", stdout);
	scanf ("%d%d", &n, &m);
	init_set ();
	for (int i = 1; i <= m; i++) {
		cin >> ch;
		// 合并
		if (ch == 'C') {
			scanf ("%d%d", &x, &y);
			if (Mp[x]|| Mp[y]) continue;
			int xx = find_set_front (x);
			int yy = find_set_front (y);
			if (xx != yy) {
				int dy = find_set_back (y);
				d2[dy] = xx;
				d1[xx] = dy;
			}
		}
		// 删除
		if (ch == 'F') {
			scanf ("%d", &x);
			if (Mp[x]) continue;
			fire (x);
		}
		// 询问
		if (ch == 'Q') {
			scanf ("%d", &x);
			if (Mp[x]) printf ("-1\n");
			else printf ("%d %d\n", find_set_front (x), find_set_back (x));
		}
	}
	return 0;
}
// 初始化
void init_set () {
	for (int i = 1; i <= n; i++) d1[i] = d2[i] = i;
}
// 查找祖先节点，可以路径压缩，直接指向祖先节点 
int find_set_front (int x) {
	if (Mp[x]) return d2[x];
	if (d1[x] != x) d1[x] = find_set_front (d1[x]);
	return d1[x];
}
// 查找儿子节点，不可以路径压缩，不然会出错 
int find_set_back (int x) {
	if (Mp[x]) return d1[x];
	if (d2[x] != x) return find_set_back (d2[x]);
	else return x;
}
void fire (int x) {
	Mp[x] = 1;
	// 后面已经被烧了 
	if (Mp[d2[x]]) return;
	fire (d2[x]);
}

$10$ 个测试点对了 $7$ 个，$70pts$ 求解，谢谢！