#P3302. [SDOI2013] 森林

    ID: 4994 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构线段树2013山东深度优先搜索DFS主席树

[SDOI2013] 森林

题目描述

小 Z 有一片森林,含有 NN 个节点,每个节点上都有一个非负整数作为权值。初始的时候,森林中有 MM 条边。

小Z希望执行 TT 个操作,操作有两类:

  • Q x y k 查询点 xx 到点 yy 路径上所有的权值中,第 kk 小的权值是多少。此操作保证点 xx 和点 yy 连通,同时这两个节点的路径上至少有 kk 个点。
  • L x y 在点 xx 和点 yy 之间连接一条边。保证完成此操作后,仍然是一片森林。

为了体现程序的在线性,我们把输入数据进行了加密。设 lastanslastans 为程序上一次输出的结果,初始的时候 lastanslastans00

对于一个输入的操作 Q x y k,其真实操作为 Q x^lastans y^lastans k^lastans

对于一个输入的操作 L x y,其真实操作为 L x^lastans y^lastans。其中 ^ 运算符表示异或,等价于 Pascal 中的 xor 运算符。

请写一个程序来帮助小 Z 完成这些操作。

输入格式

第一行包含一个正整数 testcase\mathrm{testcase},表示当前测试数据的测试点编号。

第二行包含三个整数 N,M,TN,M,T,分别表示节点数、初始边数、操作数。

第三行包含 NN 个非负整数表示 NN 个节点上的权值。

接下来 MM 行,每行包含两个整数 xxyy,表示初始的时候,点 xx 和点 yy 之间有一条无向边。

接下来 TT 行,每行描述一个操作,格式为 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,此时 lastans=0lastans=0,所以真实操作为 Q 8^0 7^0 3^0,也即 Q 8 7 3。点 88 到点 77 的路径上一共有 55 个点,其权值为 4 1 1 2 44\ 1\ 1\ 2\ 4。这些权值中,第三小的为 22,输出 22lastanslastans 变为 22

对于第二个操作 Q 3 5 1 ,此时 lastans=2lastans=2,所以真实操作为 Q 3^2 5^2 1^2,也即 Q 1 7 3。点 11 到点 77 的路径上一共有 44 个点,其权值为 1 1 2 41\ 1\ 2\ 4 。这些权值中,第三小的为 22,输出 22lastanslastans 变为 22。之后的操作类似。


数据范围

测试点编号 N,M,TN,M,T 的上界 L 操作 Q 操作 形态
11 2020 N/A N/A N/A
22 200200
343\sim 4 4×1044\times 10^4 L 操作
565\sim 6 8×1048\times 10^4
797\sim 9 保证 k=1k=1 N/A
101110\sim 11 4×1044\times 10^4 N/A
121312\sim 13 8×1048\times 10^4
141514\sim 15 4×1044\times 10^4 L 操作 N/A
161716\sim 17 8×1048\times 10^4
1818 4×1044\times 10^4 N/A
192019\sim 20 8×1048\times 10^4

注:N/A 表示没有特殊性。

对于 100%100\% 的测试数据,所有节点的编号在 1N1\sim N 的范围内。节点上的权值 109\le 10^9M<NM<N