原题在...

https://www.luogu.com.cn/problem/P11831
考虑到评测机性能差距，本题较官方赛事增加了 3 秒的额外时限。

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。

过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

题目描述
给定一个 n 个点 m 条边的有向图 G，结点由 1 至 n 编号。第 i (1≤i≤m) 条边从 u
i
​
指向 v
i
​
，保证 u
i
​
<v
i
​
。节点 j (1≤j≤n) 有两个权值 a
j
​
,b
j
​
，保证 [a
1
​
,…,a
n
​
] 与 [b
1
​
,…,b
n
​
] 均是 1∼n 的排列。

你需要进行 q 次操作。操作有以下三种：

1 x y：交换 a
x
​
和 a
y
​
；
2 x y：交换 b
x
​
和 b
y
​
；
3 x l r：你需要输出满足以下两个条件的点 y 中 b
y
​
的最大值，若不存在满足条件的点则输出 0：
l≤a
y
​
≤r。
图 G 中存在一条 x 到 y 的有向路径，即存在整数 k≥1 与 k 个结点 p
1
​
,p
2
​
,…,p
k
​
，满足 p
1
​
=x，p
k
​
=y，且对于所有 1≤i<k，图 G 中存在从 p
i
​
指向 p
i+1
​
的有向边。特别地，图 G 中总是存在一条 x 到 x 的有向路径。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 c=0。

对于每组测试数据，

第一行三个整数 n,m,q，分别表示图 G 的节点数、图 G 的边数和操作次数，
接下来 m 行，第 i (1≤i≤m) 行两个整数 u
i
​
,v
i
​
，描述一条边，
接下来一行 n 个整数 a
1
​
,a
2
​
,…,a
n
​
，描述每个节点的 a 权值，
接下来一行 n 个整数 b
1
​
,b
2
​
,…,b
n
​
，描述每个节点的 b 权值，
最后 q 行，第 i (1≤i≤q) 行三或四个整数 o
i
​
,x
i
​
,y
i
​
或 o
i
​
,x
i
​
,l
i
​
,r
i
​
，描述一次操作，格式同题目描述。
输出格式
对于每个 3 操作输出一行一个整数，表示对应操作的答案。

输入输出样例
输入 #1复制

0 1
4 4 7
1 2
1 3
2 4
3 4
4 2 3 1
1 3 2 4
3 2 1 3
3 3 2 4
1 1 4
3 1 1 3
2 2 4
3 1 2 3
3 4 1 1
输出 #1复制

4
2
3
4
0
说明/提示
【样例 1 解释】

该组样例共有 1 组测试数据。该组测试数据共包含 7 个操作。

对于第一个操作，所有满足条件的点为 2,4，因此答案为 max{b
2
​
,b
4
​
}=4。
对于第二个操作，所有满足条件的点为 3，因此答案为 b
3
​
=2。
对于第三个操作，交换 a
1
​
,a
4
​
后得到的权值序列 a 为 [1,2,3,4]。
对于第四个操作，所有满足条件的点为 1,2,3，因此答案为 max{b
1
​
,b
2
​
,b
3
​
}=3。
对于第五个操作，交换 b
2
​
,b
4
​
后得到的权值序列 b 为 [1,4,2,3]。
对于第六个操作，所有满足条件的点为 2,3，因此答案为 max{b
2
​
,b
3
​
}=4。
对于第七个操作，没有满足条件的点，因此答案为 0。
【样例 2】

见选手目录下的 recall/recall2.in 与 recall/recall2.ans。

该组样例满足测试点 1∼5 的限制。

【样例 3】

见选手目录下的 recall/recall3.in 与 recall/recall3.ans。

该组样例满足测试点 7 的限制。

【样例 4】

见选手目录下的 recall/recall4.in 与 recall/recall4.ans。

该组样例满足测试点 10∼12 的限制。

【样例 5】

见选手目录下的 recall/recall5.in 与 recall/recall5.ans。

该组样例满足测试点 13,14 的限制。

【样例 6】

见选手目录下的 recall/recall6.in 与 recall/recall6.ans。

该组样例满足测试点 18 的限制。

【样例 7】

见选手目录下的 recall/recall7.in 与 recall/recall7.ans。

该组样例满足测试点 23∼25 的限制。

【子任务】

对于所有测试点，

1≤T≤3，
1≤n,q≤10
5
，1≤m≤2×10
5
，
∀1≤i≤m，1≤u
i
​
<v
i
​
≤n，
∀1≤i≤n，1≤a
i
​
≤n，且 [a
1
​
,…,a
n
​
] 是 1∼n 的一个排列，
∀1≤i≤n，1≤b
i
​
≤n，且 [b
1
​
,…,b
n
​
] 是 1∼n 的一个排列，
∀1≤i≤q，o
i
​
∈{1,2,3}，1≤x
i
​
,y
i
​
≤n，1≤l
i
​
≤r
i
​
≤n。
测试点编号 n,q≤ m≤ 特殊性质
1∼5 2000 4000 无
6 8×10
4
1.6×10
5
AB
7 6×10
4
1.2×10
5
B
8,9 8×10
4
1.6×10
5

10∼12 AC
13,14 6×10
4
1.2×10
5
A
15,16 8×10
4
1.6×10
5

17 6×10
4
1.2×10
5
D
18 8×10
4
1.6×10
5

19,20 6×10
4
1.2×10
5
无
21,22 8×10
4
1.6×10
5

23∼25 10
5
2×10
5

特殊性质 A：∀1≤i≤q,o
i
​


=1。
特殊性质 B：∀1≤i≤q,o
i
​


=2。
特殊性质 C：∀1≤i≤q,l
i
​
=1,r
i
​
=n。
特殊性质 D：保证在每个 3 操作的时刻，∀1≤i≤n,a
i
​
=b
i
​
。
【提示】

请注意本题特别的时空限制。

附件下载
recall.zip
25.30MB