CF643D Bearish Fanpages

有一个社交网站，包含 $n$ 个粉丝专页，编号为 $1$ 到 $n$。同时有 $n$ 个公司，第 $i$ 个公司拥有第 $i$ 个粉丝专页。 最近，网站推出了一个叫“关注”的新功能。每个粉丝专页必须选择且仅选择一个其他粉丝专页进行关注。 网站不允许出现 $i$ 关注 $j$ 且 $j$ 同时关注 $i$ 的情况。同时，一个专页也不能关注自己。 假设第 $i$ 个粉丝专页关注了其他的某个专页 $j_0$。又假设有 $k$ 个其他粉丝专页 $j_1, j_2, \ldots, j_k$ 关注了 $i$。那么，当用户访问粉丝专页 $i$ 时，他们会看到来自 $k+2$ 个不同公司的广告，这些公司分别为：$i, j_0, j_1, \ldots, j_k$。恰好有 $t_i$ 人订阅（点赞）了第 $i$ 个粉丝专页，每个人都会点击恰好一个广告。对于这 $k+1$ 个公司 $j_0, j_1, \ldots, j_k$，每家公司获得 $ \left\lfloor \frac{t_i}{k+2} \right\rfloor $ 名用户点击。而剩下的 $ t_i - (k+1) \times \left\lfloor \frac{t_i}{k+2} \right\rfloor $ 名用户将点击公司 $i$（即专页所有者公司）的广告。 一个公司的总收入等于所有点击该公司广告的用户总数。 Limak 和 Radewoosh 向你寻求帮助。最初，第 $i$ 个粉丝专页关注的是 $f_i$。你需要处理 $q$ 个操作，操作有三种类型： - 1 i j — 从现在起，粉丝专页 $i$ 关注粉丝专页 $j$。保证在此次操作前，$i$ 并未关注 $j$。关于此类操作的次数有额外限制（详见输入格式）。 - 2 i — 输出第 $i$ 个公司的总收入。 - 3 — 输出两个整数，分别为所有公司当前最小收入和最大收入。

输入的第一行包含两个整数 $n$ 和 $q$（$3\leq n\leq 100000$，$1\leq q\leq 100000$），分别表示粉丝专页数量和操作数量。 第二行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$（$1\leq t_i \leq 10^{12}$），其中 $t_i$ 表示第 $i$ 个粉丝专页的订阅人数。 第三行包含 $n$ 个整数 $f_1, f_2, \ldots, f_n$（$1\leq f_i \leq n$）。最初第 $i$ 个专页关注的是 $f_i$。 接下来的 $q$ 行每行描述一个操作。每行的第一个数字为整数 $type_i$（$1\leq type_i\leq 3$），表示操作类型。 类型 1 的操作不会超过 $50000$ 次。一定存在至少一条类型 2 或类型 3 的操作（保证至少有输出）。 保证在任意时刻，一个粉丝专页不会关注自己，且不会互相关注。

对于每个类型 2 的操作，输出第 $i$ 个公司的总收入，各占据一行。对于每个类型 3 的操作，输出当前最小总收入和最大总收入，各占据一行。

在样例测试中，有 $5$ 个粉丝专页。第 $i$ 个专页有 $i\times 10$ 名订阅者。 图中的圆圈里写着订阅人数。有一条从 $A$ 指向 $B$ 的箭头，表示 $A$ 关注 $B$。 左图表示初始情况。第一个公司从自己专页获得 $5$ 的收入，从第二个专页获得 $5$ 的收入。所以总收入为 $5+5=10$。处理第一个操作（“2 1”）时，你应输出 $10$。 右图表示经过操作“1 4 2”之后（即第 $4$ 个专页开始关注第 $2$ 个专页）。此时第一公司依然从自家专页获得 $5$ 的收入，但从第二个专页只获得 $4$ 的收入。所以现在总收入是 $5+4=9$。 由 ChatGPT 5 翻译