#P10208. [2021年NK的NOI模拟]新闻的产生
[2021年NK的NOI模拟]新闻的产生
新闻的产生
题目描述
有 位记者,第 位初始有 份新闻素材,仰慕的人是 。每位记者恰好仰慕一个人,不能仰慕自己,也没有两人互相仰慕。
记者们进行一轮同时交换:每个人把素材送给他仰慕的人,以及所有仰慕他的人。若一个人初始有 份素材,要送给 个人,则给每人送 份,剩余的自己保留。送出的素材会从自己的素材中扣除。
有以下三类事件:
1 x y:将 改为 。2 x:询问按当前仰慕关系交换一轮后,第 位记者的素材数。3:询问按当前关系交换一轮后,所有记者素材数的最小值、最大值。
询问只是假设交换,不会实际改变初始素材 ;每次都从这些初始素材出发,只使用当前仰慕关系计算。
输入格式
第一行两个正整数 。
第二行 个正整数 。
第三行 个整数 。
接下来 行,每行一个事件。
输出格式
第 2 类事件输出一行一个整数。
第 3 类事件输出一行两个整数,依次为最小值和最大值。
样例 1 输入
6 8
10 20 30 40 50 60
3 5 4 5 1 3
2 1
2 3
3
2 6
1 4 6
2 3
2 6
3
样例 1 输出
23
55
22 55
37
45
40
26 45
样例说明
修改前的仰慕关系和交换后数量:

修改后的仰慕关系和交换后数量:

图中数量按记者 的顺序分别为 和 。
数据范围
- 的数据满足 。
- 的数据满足 。
- 全部数据满足 ,,,,且第 1 类事件不超过 次。关系限制在修改后也成立。