P11831 [省选联考 2025] 追忆

题目背景

考虑到评测机性能差距，本题较官方赛事增加了 3 秒的额外时限。

我常常追忆过去。

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

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

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

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

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

题目描述

给定一个 \(n\) 个点 \(m\) 条边的有向图 \(G\)，结点由 \(1\) 至 \(n\) 编号。第 \(i\) (\(1 \leq i \leq m\)) 条边从 \(u_i\) 指向 \(v_i\)，保证 \(u_i < v_i\)。节点 \(j\) (\(1 \leq j \leq n\)) 有两个权值 \(a_j, b_j\)，保证 \([a_1, \ldots, a_n]\) 与 \([b_1, \ldots, b_n]\) 均是 \(1 \sim n\) 的排列。

你需要进行 \(q\) 次操作。操作有以下三种：
- \(1\ x\ y\)：交换 \(a_x\) 和 \(a_y\)；
- \(2\ x\ y\)：交换 \(b_x\) 和 \(b_y\)；
- \(3\ x\ l\ r\)：你需要输出满足以下两个条件的点 \(y\) 中 \(b_y\) 的最大值，若不存在满足条件的点则输出 \(0\)：
1. \(l \leq a_y \leq r\)。
2. 图 \(G\) 中存在一条 \(x\) 到 \(y\) 的有向路径，即存在整数 \(k \geq 1\) 与 \(k\) 个结点 \(p_1, p_2, \ldots, p_k\)，满足 \(p_1 = x\)，\(p_k = y\)，且对于所有 \(1 \leq i < k\)，图 \(G\) 中存在从 \(p_i\) 指向 \(p_{i+1}\) 的有向边。特别地，图 \(G\) 中总是存在一条 \(x\) 到 \(x\) 的有向路径。

输入格式

本题有多组测试数据。输入的第一行两个整数 \(c, T\)，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 \(c = 0\)。

对于每组测试数据，
- 第一行三个整数 \(n, m, q\)，分别表示图 \(G\) 的节点数、图 \(G\) 的边数和操作次数，
- 接下来 \(m\) 行，第 \(i\) (\(1 \leq i \leq m\)) 行两个整数 \(u_i, v_i\)，描述一条边，
- 接下来一行 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)，描述每个节点的 \(a\) 权值，
- 接下来一行 \(n\) 个整数 \(b_1, b_2, \ldots, b_n\)，描述每个节点的 \(b\) 权值，
- 最后 \(q\) 行，第 \(i\) (\(1 \leq i \leq q\)) 行三或四个整数 \(o_i, x_i, y_i\) 或 \(o_i, x_i, l_i, r_i\)，描述一次操作，格式同题目描述。

输出格式

对于每个 \(3\) 操作输出一行一个整数，表示对应操作的答案。

输入输出样例 #1

输入 #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 \sim 5\) 的限制。

【样例 3】

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

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

【样例 4】

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

该组样例满足测试点 \(10 \sim 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 \sim 25\) 的限制。

【子任务】

对于所有测试点，
- \(1 \leq T \leq 3\)，
- \(1 \leq n, q \leq 10^5\)，\(1 \leq m \leq 2 \times 10^5\)，
- \(\forall 1 \leq i \leq m\)，\(1 \leq u_i < v_i \leq n\)，
- \(\forall 1 \leq i \leq n\)，\(1 \leq a_i \leq n\)，且 \([a_1, \ldots, a_n]\) 是 \(1 \sim n\) 的一个排列，
- \(\forall 1 \leq i \leq n\)，\(1 \leq b_i \leq n\)，且 \([b_1, \ldots, b_n]\) 是 \(1 \sim n\) 的一个排列，
- \(\forall 1 \leq i \leq q\)，\(o_i \in \{1, 2, 3\}\)，\(1 \leq x_i, y_i \leq n\)，\(1 \leq l_i \leq r_i \leq n\)。

::cute-table{tuack}

• 特殊性质 A：\(\forall 1 \leq i \leq q, o_i \neq 1\)。
• 特殊性质 B：\(\forall 1 \leq i \leq q, o_i \neq 2\)。
• 特殊性质 C：\(\forall 1 \leq i \leq q, l_i = 1, r_i = n\)。
• 特殊性质 D：保证在每个 \(3\) 操作的时刻，\(\forall 1 \leq i \leq n, a_i = b_i\)。

【提示】

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