#P17727. [2026年福建省队集训]追忆

[2026年福建省队集训]追忆

题目描述

给定一个 nn 个点 mm 条边的有向无环图 GG,结点由 11 至 nn 编号。初始时,每个点都有一个权值 aia_i。

如果在图 GG 中存在一条 xx 到 yy 的有向路径,即存在整数 k≥1k \ge 1 与 kk 个结点 p1,p2,⋯ ,pkp_1, p_2, \cdots, p_k,满足 p1=xp_1 = x,pk=yp_k = y,且对于所有 1≤i<k1 \le i < k,图 GG 中存在从 pip_i 指向 pi+1p_{i+1} 的有向边,则称 xx 能到达 yy。特别地,每个点都能到达它自己。

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

  • 1 x v1\ x\ v:将所有 xx 能到达的点的权值都改为 vv;
  • 2 x v2\ x\ v:对于所有 xx 能到达的点 yy,令 ay←min⁡(ay,v)a_y \gets \min(a_y, v);
  • 3 x3\ x:询问点 xx 当前的权值。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0c=0。

对于每组测试数据,

  • 第一行三个整数 n,m,qn, m, q,分别表示图 GG 的节点数、图 GG 的边数和操作次数,
  • 第二行 nn 个非负整数,其中第 ii 个非负整数为 aia_i,
  • 接下来 mm 行,第 ii (1≤i≤m1 \le i \le m) 行两个整数 ui,vi (ui<vi)u_i, v_i\ (u_i<v_i),描述一条边,
  • 最后 qq 行,第 ii (1≤i≤q1 \le i \le q) 行两个或三个整数 oi,xi,vio_i, x_i, v_i 或 oi,xio_i, x_i,描述一次操作,格式同题目描述。

输出格式

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

样例

样例输入 1

0 1
4 4 7
6 3 10 8
1 2
1 3
2 4
3 4
3 4
2 1 7
3 3
1 2 5
3 4
2 3 4
3 1

样例输出 1

8
7
5
6

样例解释 1

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

  • 对于第一个操作,点 44 的权值为 88,因此答案为 88。
  • 对于第二个操作,点 11 能到达的点为 1,2,3,41,2,3,4,操作后权值序列 aa 为 [6,3,7,7][6,3,7,7]。
  • 对于第三个操作,点 33 的权值为 77,因此答案为 77。
  • 对于第四个操作,点 22 能到达的点为 2,42,4,操作后权值序列 aa 为 [6,5,7,5][6,5,7,5]。
  • 对于第五个操作,点 44 的权值为 55,因此答案为 55。
  • 对于第六个操作,点 33 能到达的点为 3,43,4,操作后权值序列 aa 为 [6,5,4,4][6,5,4,4]。
  • 对于第七个操作,点 11 的权值为 66,因此答案为 66。

数据范围与提示

对于所有测试点:

  • 1≤T≤51\leq T\leq 5;
  • 1≤n,q≤2×1051\leq n,q\leq 2\times 10^5,0≤m≤2×1050\leq m\leq 2\times 10^5;
  • 对于任意 1≤i≤n1\le i\le n,0≤ai≤1090\le a_i\le 10^9;
  • 对于任意 1≤i≤m1\leq i\leq m,1≤ui<vi≤n1\leq u_i<v_i\leq n;
  • 保证给出的图是有向无环图,且没有重边;
  • 保证每次操作都有 oi∈{1,2,3}o_i\in\{1,2,3\};
  • 对于操作 1,21,2,1≤xi≤n1\leq x_i\leq n,0≤vi≤1090\leq v_i\leq 10^9;
  • 对于操作 33,1≤xi≤n1\leq x_i\leq n。
测试点编号 n≤n\le m≤m\le q≤q\le 特殊性质
1∼21\sim 2 88 2020 3030 无
3∼43\sim 4 200200 500500 600600
5∼65\sim 6 20002000 40004000
7∼87\sim 8 6×1046\times10^4 2×1052\times10^5 6×1046\times 10^4
9∼119\sim 11 8×1048\times10^4 8×1048\times 10^4
12∼1312\sim 13 10510^5 2×1052\times 10^5 10510^5
14∼1614\sim 16 2×1052\times 10^5 2×1052\times 10^5 A
17∼1817\sim 18 B
19∼2019\sim 20 C
21∼2521\sim 25 无
  • 特殊性质 A:保证 m=n−1m=n-1 且第 i(1≤i≤m)i(1\le i\le m) 条边的 ui=i,vi>iu_i=i,v_i>i;
  • 特殊性质 B:保证 oi≠1o_i\neq 1;
  • 特殊性质 C:保证 oi≠2o_i\neq 2。