OpenJudge

ffff:HJA的妹子

总时间限制:
20000ms
单个测试点时间限制:
2000ms
内存限制:
512000kB
描述

据说HJA的妹子数还没有YJQ隔壁班的妹子数多?HJA感到不服。
HJA有n个妹子,她们分别住在n间房子里。第i个妹子的漂亮值是vi
最初的时候这些房子之间有m条路。保证两个妹子之间最多只有一条简单路径。
HJA有q次操作。
Q u v k操作:HJA从第i个妹子的房子沿最短路径去第j个妹子的房子,并询问路径上经过的妹子中漂亮值第k小的妹子的漂亮值。
L u v操作:HJA让YJQ去修一条连接u和v的公路。为了体现HJA对学弟的关心,保证之前u和v不连通。
为了保证这题不会被离线水,输入中的每个u, v, k都要异或上lastanswer。开始的时候lastanswer=0。

输入
第一行一个与题目无关的整数表示YJQ的naive程度。
第二行三个整数n, m, q。
第三行n个非负整数表示第i个妹子的漂亮度。
接下来m行每行两个整数u和v表示初始时候的一条路。
接下来q行每行描述一个操作,见上。
输出
对于每个Q操作输出一行表示答案。
样例输入
9999999999999999
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 
提示
保证修改和询问操作合法。
1<=n,m,t<=80,000
vi<=1,000,000,000
另,对于真实情况,n=0
若#define HJA ZHX
则n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffg
来源
yyy

yjq naive

全局题号
7847
添加于
2015-01-17
提交次数
3
尝试人数
3
通过人数
1