#P10208. [2021年NK的NOI模拟]新闻的产生

    ID: 9324 传统题 2000ms 256MiB 尝试: 10 已通过: 2 难度: 7 上传者: 标签>数据结构图论CF2200数学模拟构造网络流

[2021年NK的NOI模拟]新闻的产生

新闻的产生

题目描述

有 NN 位记者,第 ii 位初始有 cic_i 份新闻素材,仰慕的人是 aia_i。每位记者恰好仰慕一个人,不能仰慕自己,也没有两人互相仰慕。

记者们进行一轮同时交换:每个人把素材送给他仰慕的人,以及所有仰慕他的人。若一个人初始有 cc 份素材,要送给 dd 个人,则给每人送 ⌊c/(d+1)⌋\lfloor c/(d+1)\rfloor 份,剩余的自己保留。送出的素材会从自己的素材中扣除。

有以下三类事件:

  • 1 x y:将 axa_x 改为 yy。
  • 2 x:询问按当前仰慕关系交换一轮后,第 xx 位记者的素材数。
  • 3:询问按当前关系交换一轮后,所有记者素材数的最小值、最大值。

询问只是假设交换,不会实际改变初始素材 cic_i;每次都从这些初始素材出发,只使用当前仰慕关系计算。

输入格式

第一行两个正整数 N,QN,Q。

第二行 NN 个正整数 c1,…,cNc_1,\ldots,c_N。

第三行 NN 个整数 a1,…,aNa_1,\ldots,a_N。

接下来 QQ 行,每行一个事件。

输出格式

第 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∼61\sim6 的顺序分别为 (23,22,55,33,40,37)(23,22,55,33,40,37) 和 (27,26,45,41,31,40)(27,26,45,41,31,40)。

数据范围

  • 30%30\% 的数据满足 3≤N≤5000,1≤Q≤50003\le N\le5000,1\le Q\le5000。
  • 50%50\% 的数据满足 3≤N≤30000,1≤Q≤300003\le N\le30000,1\le Q\le30000。
  • 全部数据满足 3≤N≤100000,1≤Q≤1000003\le N\le100000,1\le Q\le100000,1≤ci≤10121\le c_i\le10^{12},1≤ai,x,y≤N1\le a_i,x,y\le N,aai≠ia_{a_i}\ne i,且第 1 类事件不超过 5000050000 次。关系限制在修改后也成立。