题目描述
给定一个 n 个点 m 条边的有向无环图 G,结点由 1 至 n 编号。初始时,每个点都有一个权值 ai。
如果在图 G 中存在一条 x 到 y 的有向路径,即存在整数 k≥1 与 k 个结点 p1,p2,⋯,pk,满足 p1=x,pk=y,且对于所有 1≤i<k,图 G 中存在从 pi 指向 pi+1 的有向边,则称 x 能到达 y。特别地,每个点都能到达它自己。
你需要依次进行 q 次操作。操作有以下三种:
- 1 x v:将所有 x 能到达的点的权值都改为 v;
- 2 x v:对于所有 x 能到达的点 y,令 ay←min(ay,v);
- 3 x:询问点 x 当前的权值。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0。
对于每组测试数据,
- 第一行三个整数 n,m,q,分别表示图 G 的节点数、图 G 的边数和操作次数,
- 第二行 n 个非负整数,其中第 i 个非负整数为 ai,
- 接下来 m 行,第 i (1≤i≤m) 行两个整数 ui,vi (ui<vi),描述一条边,
- 最后 q 行,第 i (1≤i≤q) 行两个或三个整数 oi,xi,vi 或 oi,xi,描述一次操作,格式同题目描述。
输出格式
对于每个 3 操作输出一行一个整数,表示对应操作的答案。
样例
样例输入 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
该组样例共有 1 组测试数据。该组测试数据共包含 7 个操作。
- 对于第一个操作,点 4 的权值为 8,因此答案为 8。
- 对于第二个操作,点 1 能到达的点为 1,2,3,4,操作后权值序列 a 为 [6,3,7,7]。
- 对于第三个操作,点 3 的权值为 7,因此答案为 7。
- 对于第四个操作,点 2 能到达的点为 2,4,操作后权值序列 a 为 [6,5,7,5]。
- 对于第五个操作,点 4 的权值为 5,因此答案为 5。
- 对于第六个操作,点 3 能到达的点为 3,4,操作后权值序列 a 为 [6,5,4,4]。
- 对于第七个操作,点 1 的权值为 6,因此答案为 6。
数据范围与提示
对于所有测试点:
- 1≤T≤5;
- 1≤n,q≤2×105,0≤m≤2×105;
- 对于任意 1≤i≤n,0≤ai≤109;
- 对于任意 1≤i≤m,1≤ui<vi≤n;
- 保证给出的图是有向无环图,且没有重边;
- 保证每次操作都有 oi∈{1,2,3};
- 对于操作 1,2,1≤xi≤n,0≤vi≤109;
- 对于操作 3,1≤xi≤n。
| 测试点编号 |
n≤ |
m≤ |
q≤ |
特殊性质 |
| 1∼2 |
8 |
20 |
30 |
无 |
| 3∼4 |
200 |
500 |
600 |
| 5∼6 |
2000 |
4000 |
| 7∼8 |
6×104 |
2×105 |
6×104 |
| 9∼11 |
8×104 |
8×104 |
| 12∼13 |
105 |
2×105 |
105 |
| 14∼16 |
2×105 |
2×105 |
A |
| 17∼18 |
B |
| 19∼20 |
C |
| 21∼25 |
无 |
- 特殊性质 A:保证 m=n−1 且第 i(1≤i≤m) 条边的 ui=i,vi>i;
- 特殊性质 B:保证 oi=1;
- 特殊性质 C:保证 oi=2。