#P11831. [省选联考 2025] 追忆

[省选联考 2025] 追忆

题目背景

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

我常常追忆过去。

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

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

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

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

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

题目描述

给定一个 nn 个点 mm 条边的有向图 GG,结点由 11nn 编号。第 ii (1im1 \leq i \leq m) 条边从 uiu_i 指向 viv_i,保证 ui<viu_i < v_i。节点 jj (1jn1 \leq j \leq n) 有两个权值 aj,bja_j, b_j,保证 [a1,,an][a_1, \ldots, a_n][b1,,bn][b_1, \ldots, b_n] 均是 1n1 \sim n 的排列。

你需要进行 qq 次操作。操作有以下三种:

  • 1 x y1\ x\ y:交换 axa_xaya_y
  • 2 x y2\ x\ y:交换 bxb_xbyb_y
  • 3 x l r3\ x\ l\ r:你需要输出满足以下两个条件的点 yybyb_y 的最大值,若不存在满足条件的点则输出 00
    1. layrl \leq a_y \leq r
    2. GG 中存在一条 xxyy 的有向路径,即存在整数 k1k \geq 1kk 个结点 p1,p2,,pkp_1, p_2, \ldots, p_k,满足 p1=xp_1 = xpk=yp_k = y,且对于所有 1i<k1 \leq i < k,图 GG 中存在从 pip_i 指向 pi+1p_{i+1} 的有向边。特别地,图 GG 中总是存在一条 xxxx 的有向路径。

输入格式

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

对于每组测试数据,

  • 第一行三个整数 n,m,qn, m, q,分别表示图 GG 的节点数、图 GG 的边数和操作次数,
  • 接下来 mm 行,第 ii (1im1 \leq i \leq m) 行两个整数 ui,viu_i, v_i,描述一条边,
  • 接下来一行 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n,描述每个节点的 aa 权值,
  • 接下来一行 nn 个整数 b1,b2,,bnb_1, b_2, \ldots, b_n,描述每个节点的 bb 权值,
  • 最后 qq 行,第 ii (1iq1 \leq i \leq q) 行三或四个整数 oi,xi,yio_i, x_i, y_ioi,xi,li,rio_i, x_i, l_i, r_i,描述一次操作,格式同题目描述。

输出格式

对于每个 33 操作输出一行一个整数,表示对应操作的答案。

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
4
2
3
4
0

提示

【样例 1 解释】

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

  • 对于第一个操作,所有满足条件的点为 2,42, 4,因此答案为 max{b2,b4}=4\max\{b_2, b_4\} = 4
  • 对于第二个操作,所有满足条件的点为 33,因此答案为 b3=2b_3 = 2
  • 对于第三个操作,交换 a1,a4a_1, a_4 后得到的权值序列 aa[1,2,3,4][1, 2, 3, 4]
  • 对于第四个操作,所有满足条件的点为 1,2,31, 2, 3,因此答案为 max{b1,b2,b3}=3\max\{b_1, b_2, b_3\} = 3
  • 对于第五个操作,交换 b2,b4b_2, b_4 后得到的权值序列 bb[1,4,2,3][1, 4, 2, 3]
  • 对于第六个操作,所有满足条件的点为 2,32, 3,因此答案为 max{b2,b3}=4\max\{b_2, b_3\} = 4
  • 对于第七个操作,没有满足条件的点,因此答案为 00

【样例 2】

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

该组样例满足测试点 151 \sim 5 的限制。

【样例 3】

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

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

【样例 4】

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

该组样例满足测试点 101210 \sim 12 的限制。

【样例 5】

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

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

【样例 6】

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

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

【样例 7】

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

该组样例满足测试点 232523 \sim 25 的限制。

【子任务】

对于所有测试点,

  • 1T31 \leq T \leq 3
  • 1n,q1051 \leq n, q \leq 10^51m2×1051 \leq m \leq 2 \times 10^5
  • 1im\forall 1 \leq i \leq m1ui<vin1 \leq u_i < v_i \leq n
  • 1in\forall 1 \leq i \leq n1ain1 \leq a_i \leq n,且 [a1,,an][a_1, \ldots, a_n]1n1 \sim n 的一个排列,
  • 1in\forall 1 \leq i \leq n1bin1 \leq b_i \leq n,且 [b1,,bn][b_1, \ldots, b_n]1n1 \sim n 的一个排列,
  • 1iq\forall 1 \leq i \leq qoi{1,2,3}o_i \in \{1, 2, 3\}1xi,yin1 \leq x_i, y_i \leq n1lirin1 \leq l_i \leq r_i \leq n
测试点编号 n,qn, q \leq mm \leq 特殊性质
151 \sim 5 20002\,000 40004\,000
66 8×1048 \times 10^4 1.6×1051.6 \times 10^5 AB
77 6×1046 \times 10^4 1.2×1051.2 \times 10^5 B
8,98, 9 8×1048 \times 10^4 1.6×1051.6 \times 10^5
101210 \sim 12 AC
13,1413, 14 6×1046 \times 10^4 1.2×1051.2 \times 10^5 A
15,1615, 16 8×1048 \times 10^4 1.6×1051.6 \times 10^5
1717 6×1046 \times 10^4 1.2×1051.2 \times 10^5 D
1818 8×1048 \times 10^4 1.6×1051.6 \times 10^5
19,2019, 20 6×1046 \times 10^4 1.2×1051.2 \times 10^5
21,2221, 22 8×1048 \times 10^4 1.6×1051.6 \times 10^5
232523 \sim 25 10510^5 2×1052 \times 10^5
  • 特殊性质 A:1iq,oi1\forall 1 \leq i \leq q, o_i \neq 1
  • 特殊性质 B:1iq,oi2\forall 1 \leq i \leq q, o_i \neq 2
  • 特殊性质 C:1iq,li=1,ri=n\forall 1 \leq i \leq q, l_i = 1, r_i = n
  • 特殊性质 D:保证在每个 33 操作的时刻,1in,ai=bi\forall 1 \leq i \leq n, a_i = b_i

【提示】

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