← 返回题目列表

Codeforces · 643/D

D. 看跌粉丝专页

中文机器翻译题面 查看原题

有一个社交网站,有 n 个粉丝专页,编号为 1 到 n。还有 n 个公司,第 i 个公司拥有第 i 个粉丝专页。

最近,该网站创建了一个名为“关注”的功能。每个粉丝专页必须准确选择一个其他粉丝专页来关注。

该网站不允许出现 i 跟随 j 并且同时 j 跟随 i 的情况。此外,粉丝专页无法关注自身。

假设粉丝专页 i 关注其他一些粉丝专页 j0。另外,假设 i 后面有 k 个其他粉丝专页 j1、j2、...、jk。然后,当人们访问粉丝页面 i 时,他们会看到来自 k + 2 个不同公司的广告:i、j0、j1、...、jk。正好有 ti 个人订阅(喜欢)第 i 个粉丝页面,并且每个人都会点击一个添加。对于 k + 1 个公司 j0, j1, ..., jk 中的每一个,$$\left\lfloor \frac{t_i}{k+2} \right\rfloor$$ 人们将会点击他们的广告。剩余的 $$t_{i}-(k+1)\cdot\left[\frac{t_{i}}{k+2}\right]$$ 人将点击公司 i(粉丝专页所有者)的广告。

公司的总收入等于点击该公司广告的人数。

利马克和拉德伍什向你寻求帮助。最初,粉丝专页 i 跟随粉丝专页 fi。您的任务是处理三种类型的 q 查询:

- 1 i j — 粉丝专页 i 从现在开始关注粉丝专页 j。保证我在查询之前没有跟随 j 。请注意这种类型的查询数量的额外限制(下面的“输入”部分)。
- 2 i — 打印第 i 个公司的总收入。
- 3 — 打印两个整数:一家公司的最小收入和一家公司的最大收入。

输入

输入的第一行包含两个整数 n 和 q (3 ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000)——分别是粉丝页面的数量和查询的数量。

第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 1012),其中 ti 表示订阅第 i 个粉丝专页的人数。

第三行包含 n 个整数 f1, f2, ..., fn (1 ≤ fi ≤ n)。最初,粉丝专页 i 跟随粉丝专页 fi。

然后是 q 行。其中第 i 个描述第 i 个查询。该行中的第一个数字是整数 typei (1 ≤ typei ≤ 3) — 查询的类型。

第一类型的查询最多为 50 000 个。至少会有一个第二或第三类型的查询(因此,输出不会为空)。

保证每个时刻粉丝页面都不会关注自己,并且不会有两个粉丝页面互相关注。

输出

对于第二种类型的每个查询,在单独的行中打印一个整数 - 给定公司的总收入。对于第三种类型的每个查询,在单独的行中打印两个整数 - 分别是最小和最大总收入。

示例

输入 #1

5 12
10 20 30 40 50
2 3 4 5 2
2 1
2 2
2 3
2 4
2 5
1 4 2
2 1
2 2
2 3
2 4
2 5
3

输出 #1

10
36
28
40
36
9
57
27
28
29
9 57

注意

在样本测试中,有 5 个粉丝专页。其中第 i 个有 i·10 个订户。

在附图上,订阅者的数量写在圆圈中。从 A 到 B 的箭头表示 A 跟随 B。

左图显示了初始情况。第一家公司从自己的粉丝页面获得收入 $$10 - \left\lfloor \frac{10}{2} \right\rfloor = 5$$,并从第二个粉丝页面获得收入 $$\left\lfloor \frac { 20 } { 4 } \right\rfloor = 5$$。因此,总收入为 5 + 5 = 10。在第一个查询(“2 1”)之后,您应该打印 10。

右图显示了查询“1 4 2”之后的情况(之后粉丝专页 4 紧随粉丝专页 2)。然后,第一家公司仍然从自己的粉丝页面获得收入 5,但现在它只从第二个粉丝页面获得 $$\left\lfloor \frac { 20 } { 5 } \right\rfloor = 4$$。所以,现在总收入是5+4=9。