原题在...

原题链接：101467.「联合省选 2025」追忆

199****0937

2026-01-23 19:52:29

发布于：江苏

49阅读

0回复

0点赞

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

有帮助，赞一个

去预览

0/2000

全部评论 7

Xylophone
吓哭了

5天前来自广东
2
- ༺དༀ༒∞░∞༒ༀཌ༻（不加团）
  回复
  Xylophone
  我该在哪停留
  
  5天前来自浙江
  0
- 199****0937
  回复
  Xylophone
  
  5天前来自江苏
  0
- Xylophone
  回复
  ༺དༀ༒∞░∞༒ༀཌ༻（不加团）
  我问我自己
  
  5天前来自广东
  1
cjdst
我常常追忆过去。

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

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

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

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

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

5天前来自广东
1
想要AC
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$ ：

$l \leq a_y \leq r$ 。

图 $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_
15小时前来自福建
0
cjdst
有一道题，是黑题，出现于2025年CCF官方比赛，nqlogn20pts，nq100pts，这题是什么

5天前来自广东
0
- cjdst
  回复
  cjdst
  是 query，你们猜对了吗（（（
  
  5天前来自广东
  0
- cjdst
  回复
  cjdst
  我去追忆好像可以 $O(n^2\log n)$ ，下巴掉下来
  
  15小时前来自广东
  0
Xylophone
ACGO把精髓去掉了

5天前来自广东
0
- cjdst
  回复
  Xylophone
  我去，这个 ACGO 怎么这么坏啊
  
  5天前来自广东
  1
- Xylophone
  回复
  cjdst
  ACGO 评测姬最慢的一集
  
  5天前来自广东
  0
- Xylophone
  回复
  cjdst
  ACGO 把天使玩偶搬了然后被跑进几十毫秒这个 ACGO 真坏呀他们为什么要打架
  
  5天前来自广东
  0
Xylophone
为什么不复制Markdown

5天前来自广东
0
199****0937
我问我自己

5天前来自江苏
0

全部评论 7

P11831 [省选联考 2025] 追忆

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

热门讨论