#P3302. [SDOI2013] 森林
[SDOI2013] 森林
题目描述
小 Z 有一片森林,含有 个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有 条边。
小Z希望执行 个操作,操作有两类:
Q x y k
查询点 到点 路径上所有的权值中,第 小的权值是多少。此操作保证点 和点 连通,同时这两个节点的路径上至少有 个点。L x y
在点 和点 之间连接一条边。保证完成此操作后,仍然是一片森林。
为了体现程序的在线性,我们把输入数据进行了加密。设 为程序上一次输出的结果,初始的时候 为 。
对于一个输入的操作 Q x y k
,其真实操作为 Q x^lastans y^lastans k^lastans
。
对于一个输入的操作 L x y
,其真实操作为 L x^lastans y^lastans
。其中 ^
运算符表示异或,等价于 Pascal 中的 xor
运算符。
请写一个程序来帮助小 Z 完成这些操作。
输入格式
第一行包含一个正整数 ,表示当前测试数据的测试点编号。
第二行包含三个整数 ,分别表示节点数、初始边数、操作数。
第三行包含 个非负整数表示 个节点上的权值。
接下来 行,每行包含两个整数 和 ,表示初始的时候,点 和点 之间有一条无向边。
接下来 行,每行描述一个操作,格式为 Q x y k
或者 L x y
,其含义见题目描述部分。
输出格式
对于每一个第一类操作,输出一个非负整数表示答案。
1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3
Q 3 5 1
Q 10 0 0
L 5 4
L 3 2
L 0 7
Q 9 2 5
Q 6 1 6
2
2
1
4
2
提示
样例解释
对于第一个操作 Q 8 7 3
,此时 ,所以真实操作为 Q 8^0 7^0 3^0
,也即 Q 8 7 3
。点 到点 的路径上一共有 个点,其权值为 。这些权值中,第三小的为 ,输出 , 变为 。
对于第二个操作 Q 3 5 1
,此时 ,所以真实操作为 Q 3^2 5^2 1^2
,也即 Q 1 7 3
。点 到点 的路径上一共有 个点,其权值为 。这些权值中,第三小的为 ,输出 , 变为 。之后的操作类似。
数据范围
测试点编号 | 的上界 | L 操作 |
Q 操作 |
形态 |
---|---|---|---|---|
N/A | N/A | N/A | ||
无 L 操作 |
链 | |||
保证 | N/A | |||
N/A | ||||
无 L 操作 |
N/A | |||
N/A | ||||
注:N/A 表示没有特殊性。
对于 的测试数据,所有节点的编号在 的范围内。节点上的权值 。。