徐老师的银白森林plus
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
在不知名的银白森林，共有 $n$ 个节点。每个节点处生活着一名魔法师，但是有一天，魔王占领了银白森林，准备使用魔化权杖将所有的魔法师魔化！
而自从上次去过银白森林后，徐老师对于这些给予他祝福的魔法师还是非常有好感的
于是徐老师决定去拯救这些魔法师和银白森林！
经过徐老师的努力，徐老师得到了两个神器——探视之眼，净化权杖！
探视之眼可以让徐老师实时的观测到整个森林的状态，以及魔王的动向，徐老师发现，银白森林的道路被魔王进行了修改，不再是每个节点有一条道路连向其他节点，而变成了无规律的 $m$ 条单向道路
同时，魔王的魔化权杖的作用如下：魔王可以选择一个节点 $x$ 释放强度为 $y$ 的魔气，然后魔气会顺着单向道路一直扩散到所有可到达的节点，将所有碰到这股魔气的魔法师全部魔化！被这股魔气魔化的魔法师的魔化值均会变成 $y$
并且徐老师发现后释放的魔气优先级一定高于先释放的，也就是如果一名魔法师一开始的魔气值是 $10$，而他后来又被强度为 $5$ 的魔气魔化了一次，那么他的魔气值将会变成 $5$，而后他又被强度为 $15$ 的魔气魔化了一次，他的魔气值又会变成 $15$
而徐老师的净化权杖效果和魔化权杖类似：徐老师可以选择一个节点 $x$ 释放强度为 $y$ 的净化之力，然后净化之力会沿着单向道路一直扩散到所有可到达的节点，将所有碰到这股净化之力的魔法师进行净化，但是由于徐老师的实力不足，只能将所有魔气值高于 $y$ 的魔法师的魔气值降低到 $y$，对魔气值低于 $y$ 的魔法师无效，所以碰到这股净化之力的魔法师的魔气值将会变成 $min(原本的魔气值,y)$
现在依次给出魔王和徐老师分别使用权杖的时刻表，在其中，徐老师想实时的知道某个魔法师的魔气值现在为多少，请你帮帮他
P.S. 一开始所有魔法是均没有被魔化，魔气值即为 $0$
输入格式
输入第一行包含三个整数 $n,m,q$，表示银白森林有 $n$ 个节点，$m$ 条单向边，时刻表共有 $q$ 次操作接下来 $m$ 行，每行包含两个整数 $u,v$ 表示一条从 $u$ 到 $v$ 的单向道路
接下来 $q$ 行，每行表示一次操作，操作共有三种格式：
$1\ x\ y$ 表示魔王在节点 $x$ 处使用了一次魔化权杖，魔气强度为 $y$
$2\ x\ y$ 表示徐老师在节点 $x$ 处使用了一次净化权杖，净化之力强度为 $y$
$3\ x$ 表示徐老师想知道此时节点 $x$ 处魔法师的魔化值
对于 $20\%$ 的数据，$1 \le n, m, q \le 5000$；
对于另外 $10\%$ 的数据，没有 $1$ 操作；
对于另外 $10\%$ 的数据，没有 $2$ 操作且 $1 \le n, m, q \le 50000$；
对于另外 $20\%$ 的数据，没有 $2$ 操作；
对于另外 $20\%$ 的数据，$1 \le n, m, q \le 50000$；
对于 $100\%$ 的数据，$1 \le n, m, q \le 10^5, 1 \le u \le n, 0 \le x \le 10^9$。
输出格式
对于每个询问输出对应的答案样例
6 5 12
1 2
1 3
3 4
2 4
5 6
1 1 3
3 1
3 2
1 2 2
3 3
3 4
2 6 7
3 5
3 6
2 1 3
3 2
3 33
3
3
2
0
0
2
3提示
1. 魔王在 $1$ 号节点释放强度为 $3$ 的魔气，所有节点的魔气值为 $[3,3,3,3,0,0]$2. 查询 $1$ 号点的魔气值为 $3$
3. 查询 $2$ 号点的魔气值为 $3$
4. 在 $2$ 号节点释放强度为 $2$ 的魔气，所有节点的魔气值为 $[3,2,3,2,0,0]$
5. 查询 $3$ 号点的魔气值为 $3$
6. 查询 $4$ 号点的魔气值为 $2$
7. 徐老师在 $6$ 号节点释放强度为 $7$ 的净化之力，所有节点的魔气值为 $[3,2,3,2,0,0]$
8. 查询 $5$ 号点的魔气值为 $0$
9. 查询 $6$ 号点的魔气值为 $0$
10. 徐老师在 $1$ 号节点释放强度为 $3$ 的净化之力，所有节点的魔气值为 $[3,2,3,2,0,0]$
11. 查询 $2$ 号点的魔气值为 $2$
12. 查询 $3$ 号点的魔气值为 $3$
23CSP-S秋季提高组模拟赛(5)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-10-1 17:30
- 结束于
- 2023-10-11 17:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 23
