#PQJ1929x10148. QOJ 1929_10148
QOJ 1929_10148
2025 联合省选 第一试追忆(recall) 追忆(recall) 【题目背景】 我常常追忆过去。 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲,揉捻成天上朵朵白云。 云朵之间亦有分别:积云厚重,而卷云飘渺。生命里震撼的场景掠过我的思绪便一 生无法忘怀,而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦, 太过清楚则无法愉悦自己的幻想,过分模糊却又坠入虚无。只有薄雾间的山水,面纱下 的女子,那恰到好处的朦胧,才能满足我对美的苛求。 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友,推倒又重建的街道, 种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来, 我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间,在一个场景前 驻足,在岁月的朦胧里瞭望过去的自己,感受尽可能多的甜蜜。美好的时光曾流过我的 身体,我便心满意足。 过去已经凝固,我带着回忆向前,只是时常疏于保管,回忆也在改变着各自的形态。 这给我的追忆旅程带来些许挑战。 我该在哪里停留?我问我自己。 【题目描述】 给定一个n 个点m 条边的有向图G,结点由1 至n 编号。第i (1 ≤i ≤m) 条边 从ui 指向vi,保证ui < vi。节点j (1 ≤j ≤n) 有两个权值aj, bj,保证[a1, . . . , an] 与 [b1, . . . , bn] 均是1 ∼n 的排列。 你需要进行q 次操作。操作有以下三种: • 1 x y:交换ax 和ay; • 2 x y:交换bx 和by; • 3 x l r:你需要输出满足以下两个条件的点y 中by 的最大值,若不存在满足 条件的点则输出0:
- l ≤ay ≤r。
- 图G 中存在一条x 到y 的有向路径,即存在整数k ≥1 与k 个结点 p1, p2, . . . , pk,满足p1 = x,pk = y,且对于所有1 ≤i < k,图G 中存在 从pi 指向pi+1 的有向边。特别地,图G 中总是存在一条x 到x 的有向 路径。 【输入格式】 从文件recall.in 中读入数据。 第5 页 共12 页
2025 联合省选 第一试追忆(recall) .本.题.有.多.组.测.试.数.据。输入的第一行两个整数c, T,分别表示测试点编号和测试数 据组数,接下来输入每组测试数据。样例满足c = 0。 对于每组测试数据, • 第一行三个整数n, m, q,分别表示图G 的节点数、图G 的边数和操作次数, • 接下来m 行,第i (1 ≤i ≤m) 行两个整数ui, vi,描述一条边, • 接下来一行n 个整数a1, a2, . . . , an,描述每个节点的a 权值, • 接下来一行n 个整数b1, b2, . . . , bn,描述每个节点的b 权值, • 最后q 行,第i (1 ≤i ≤q) 行三或四个整数oi, xi, yi 或oi, xi, li, ri,描述一次操 作,格式同题目描述。 【输出格式】 输出到文件recall.out 中。 对于每个3 操作输出一行一个整数,表示对应操作的答案。 【样例1 输入】 1 0 1 2 4 4 7 3 1 2 4 1 3 5 2 4 6 3 4 7 4 2 3 1 8 1 3 2 4 9 3 2 1 3 10 3 3 2 4 11 1 1 4 12 3 1 1 3 13 2 2 4 14 3 1 2 3 15 3 4 1 1 【样例1 输出】 1 4 2 2 3 3 第6 页 共12 页
2025 联合省选 第一试追忆(recall) 4 4 5 0 【样例1 解释】 该组样例共有1 组测试数据。该组测试数据共包含7 个操作。 • 对于第一个操作,所有满足条件的点为2, 4,因此答案为max{b2, b4} = 4。 • 对于第二个操作,所有满足条件的点为3,因此答案为b3 = 2。 • 对于第三个操作,交换a1, a4 后得到的权值序列a 为[1, 2, 3, 4]。 • 对于第四个操作,所有满足条件的点为1, 2, 3,因此答案为max{b1, b2, b3} = 3。 • 对于第五个操作,交换b2, b4 后得到的权值序列b 为[1, 4, 2, 3]。 • 对于第六个操作,所有满足条件的点为2, 3,因此答案为max{b2, b3} = 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 页 共12 页
2025 联合省选 第一试追忆(recall) 【样例7】 见选手目录下的recall/recall7.in 与recall/recall7.ans。 该组样例满足测试点23 ∼25 的限制。 【子任务】 对于所有测试点, • 1 ≤T ≤3, • 1 ≤n, q ≤105,1 ≤m ≤2 × 105, • ∀1 ≤i ≤m, 1 ≤ui < vi ≤n, • ∀1 ≤i ≤n, 1 ≤ai ≤n,且[a1, . . . , an] 是1 ∼n 的一个排列, • ∀1 ≤i ≤n, 1 ≤bi ≤n,且[b1, . . . , bn] 是1 ∼n 的一个排列, • ∀1 ≤i ≤q, oi ∈{1, 2, 3}, 1 ≤xi, yi ≤n, 1 ≤li ≤ri ≤n。 测试点编号 n, q ≤ m ≤ 特殊性质 1 ∼5 2,000 4,000 无 6 8 ×104 1.6 ×105 AB 7 6 ×104 1.2 ×105 B 8, 9 8 ×104 1.6 ×105 10 ∼12 AC 13, 14 6 ×104 1.2 ×105 A 15, 16 8 ×104 1.6 ×105 17 6 ×104 1.2 ×105 D 18 8 ×104 1.6 ×105 19, 20 6 ×104 1.2 ×105 无 21, 22 8 ×104 1.6 ×105 23 ∼25 105 2 ×105 特殊性质A:∀1 ≤i ≤q, oi̸ = 1。 特殊性质B:∀1 ≤i ≤q, oi̸ = 2。 特殊性质C:∀1 ≤i ≤q, li = 1, ri = n。 特殊性质D:保证在每个3 操作的时刻,∀1 ≤i ≤n, ai = bi。 【提示】 请注意本题特别的时空限制。 第8 页 共12 页