{"problem":{"name":"Two Operations","description":{"content":"在一次聚会上，一共有 $n$ 名学生，他们的编号分别为 $1,2,3,\\cdots,n$，他们被分成 $k$ 组，组的编号分别为 $1,2,3,\\ldots,k$。 小 V 老师负责组织这场聚会，在聚会的开始，第 $i$ 名学生被分到了第 $a_i$ 组，并拿到了 $b_i$ 颗糖果。（小 V 既不属于任何组别，也没有任何糖果。在接下来的活动中，小 V 作为组织者的身份。）  这一次聚会一共有","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8379"},"statements":[{"statement_type":"Markdown","content":"在一次聚会上，一共有 $n$ 名学生，他们的编号分别为 $1,2,3,\\cdots,n$，他们被分成 $k$ 组，组的编号分别为 $1,2,3,\\ldots,k$。\n\n小 V 老师负责组织这场聚会，在聚会的开始，第 $i$ 名学生被分到了第 $a_i$ 组，并拿到了 $b_i$ 颗糖果。（小 V 既不属于任何组别，也没有任何糖果。在接下来的活动中，小 V 作为组织者的身份。） \n\n这一次聚会一共有 $m$ 轮活动，对于每一轮活动，可能发生以下两种情况之一：\n\n1.  `Change X Y`，表示把所有组别为 $X$ 的学生的组别改为 $Y$（修改后 $X$ 即为空组），并把组 $X$ **删除**。\n2.  `Query`，表示小 V 想要知道，如果把**剩下**的组合并（定义见下） 成一大组，那么这一大组内**拥有最多糖果的学生的糖果数最少可能是多少**。\n\n定义一个组 $G_i$ 的大小就是这个组内含有学生的个数，记为 $S_i$。\n\n**合并**：将大小为 $S_1(S_1>0)$ 的组 $G_1$ 合并到大小为 $S_2(S_2>0)$ 的组 $G_2$，其中 $G_1$ 组内所有学生拥有糖果数之和为 $f$，则：\n\n1. 第一步，将原先 $G_1$ 中所有学生的糖果数都变为 $0$，并将他们的组别改为 $G_2$。\n2. 第二步，将目前 $G_2$ 中每位学生（包括原先 $G_1$ 中的学生）的糖果数加上 $\\dfrac{f}{S_1+S_2}$（糖果数不一定为整数块）。\n\n**注意：**\n\n1. $G_1$ 合并到 $G_2$ 的最后结果可能会与 $G_2$ 合并到 $G_1$ 的最后结果不同。\n2. `Query` 中的合并不会真实发生。即在这一次情况过后，所有学生的糖果数与所在组与此次操作未发生前一致。\n\n请将每次 `Query` 中的答案对 $10^9+7$ 取模。（可能是分数取模，如果不知道如何取模请见**提示说明**）\n\n## Input\n\n第一行三个整数 $n,m,k$。\n\n第二行 $n$ 个整数 $a_{1\\ldots n}$。\n\n第三行 $n$ 个整数 $b_{1\\ldots n}$。\n\n接下来 $m$ 行，每行对应一种情况。具体格式参见题目描述或输入输出样例。\n\n## Output\n\n输出若干行整数表示答案。\n\n[samples]\n\n## Background\n\n**本题时限较小，请采用较快的读入方式，以下是出题人提供的快读模板：**\n\n```cpp\ntypedef long long LL;\ninline LL read(){\n\tregister LL x=0,f=1;\n\tchar c=getchar();\n\twhile(c<'0'||c>'9'){\n\t\tif(c=='-') f=-1;\n\t\tc=getchar();\n\t}\n\twhile(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();\n\treturn x*f;\n}\n```\n\n当然你也可以采用自己的读入方法。\n\n## Note\n\n【样例解释】\n\n第一次 `Query` 时，将第二组合并到第一组，此时三名学生的糖果数分别为 $\\dfrac{14}{3},\\dfrac{17}{3},\\dfrac{5}{3}$，糖果数最多的同学有 $\\dfrac{17}{3}$ 块糖果，取到了最小值，对 $10^9+7$ 取模后为 $666666677$。\n\n第二次 `Query` 时，所有学生都在同一组，而糖果数最多的同学有 $5$ 块糖果。\n\n---\n\n【数据范围】\n\n| 数据点 | $n$  | $m$  | $k$  | $a_i$ | $b_i$  |\n| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |\n| $1$ | $\\le 10$ |无特殊限制 | $\\le 10$ | $\\le 10$ | $\\le 100$ |\n| $2$ | $\\le 100$ | $\\le 10$ | $\\le 100$ | $\\le 100$ | $\\le 100$ |\n| $3$ | $\\le 10^5$ | $=1$ | $\\le 10^5$ | $\\le 10^5$ | $\\le 10^5$ |\n| $4$ | $\\le 10^5$ | 无特殊限制 | $=1$ | $=1$ | $\\le10^5$ |\n| $5$ | $\\le 10^3$ |无特殊限制 | $\\le 5$ | $\\le 5$ | $\\le 100$ |\n| $6$ | $\\le 10^4$ | $\\le 10^3$ | $\\le 10^4$ | $\\le 10^4$ | $\\le 10^5$ |\n| $7$ | $\\le 10^4$ | $\\le 5\\times10^3$ | $\\le 10^4$ | $\\le 10^4$ | $\\le 10^5$ |\n| $8$ | $\\le 10^5$ | 无特殊限制 | $\\le 10^5$ | $\\le 10^5$ | $\\le 10^5$ |\n| $9 $| $\\le 5\\times10^5$ | 无特殊限制 | $5\\times10^5$ | $5\\times10^5$ | $\\le 10^5$ |\n| $10$ | $\\le 10^6$ | 无特殊限制 | $\\le 10^6$ | $\\le 10^6$ | $\\le 10^5$ |\n\n对于 $100\\%$ 的数据，满足 $1 \\leq n \\leq 10^6,\\ 1\\leq m \\leq 2\\times k-1,\\ 1 \\leq a_i\\leq k \\leq n,\\ 1 \\leq b_i \\leq 10^5$。**数据保证合法，初始时每组是非空的。**\n\n不熟悉有理数取模的请看[此处](/problem/solution/P2613)。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8379","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 3 2\n1 1 2\n3 4 5\nQuery\nChange 2 1\nQuery","666666677\n5"]],"created_at":"2026-03-03 11:09:25"}}