#PQJ209x4125. QOJ 209_4125
QOJ 209_4125
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮 第一试 森林 森林 【问题描述】 小Z 有一片森林,含有N 个节点,每个节点上都有一个非负整数作为权值。 初始的时候,森林中有M 条边。 小Z 希望执行T 个操作,操作有两类: 1、Q x y k 查询点x 到点y 路径上所有的权值中,第k 小的权值是多少。此 操作保证点x 和点y 连通,同时这两个节点的路径上至少有k 个点。 2、L x y 在点x 和点y 之间连接一条边。保证完成此操作后,仍然是一片森 林。 为了体现程序的在线性,我们把输入数据进行了加密。设lastans 为程序上 一次输出的结果,初始的时候lastans 为0。 对于一个输入的操作Q x y k,其真实操作为Q x^lastans y^lastans k^lastans。 对于一个输入的操作L x y,其真实操作为L x^lastans y^lastans。 其中^运算符表示异或,等价于pascal 中的xor 运算符。 请写一个程序来帮助小Z 完成这些操作。 【输入格式】 第一行包含一个正整数testcase,表示当前测试数据的测试点编号。保证1 ≤testcase≤20。 第二行包含三个整数N,M,T,分别表示节点数、初始边数、操作数。 第三行包含N 个非负整数表示N 个节点上的权值。 接下来M 行,每行包含两个整数x 和y,表示初始的时候,点x 和点y 之 间有一条无向边。 接下来T 行,每行描述一个操作,格式为“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
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮 第一试 森林 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 1 7 3 Q 8 2 2 L 4 5 L 2 3 L 1 6 Q 8 3 4 Q 2 5 2
对于第一个操作 Q 8 7 3,此时lastans=0,所以真实操作为Q 8^0 7^0 3^0, 也即Q 8 7 3。点8 到点7 的路径上一共有5 个点,其权值为4 1 1 2 4。这些权值 中,第三小的为2,输出2,lastans 变为2。 对于第二个操作 Q 3 5 1,此时lastans=2,所以真实操作为Q 3^2 5^2 1^2, 也即Q 1 7 3。点1 到点7 的路径上一共有4 个点,其权值为1 1 2 4。这些权值 中,第三小的为2,输出2,lastans 变为2。 之后的操作类似。
全国青少年信息学奥林匹克
山东省省队选拔赛2013 第一轮 第一试 森林
【数据规模和约定】 测试点编号 N、M、T 的上界 L 操作 Q 操作 形态 1 20 N/A N/A N/A 2 200 3 4104 无L 操作 链 4 4104 5 8104 6 8104 7 8104 保证k=1 N/A 8 8104 9 8104 10 4104 N/A 11 4104 12 8104 13 8104 14 4104 无L 操作 N/A 15 4104 16 8104 17 8104 18 4104 N/A 19 8104 20 8104
注:N/A 表示没有特殊性
对于100%的测试数据:所有节点的编号在1..N 的范围内。节点上的权值≤109。 M<N。