{"problem":{"name":"[XJTUPC 2024] Everyone's ALL IN","description":{"content":" 女士们，先生们。 早上好，中午好，以及晚上好。 欢迎来到“好得不能再好了！泰拉大师投资课”，我是你们的坎老师。 不要 10000，不要 5000，只需要 999 源石锭，一对一指导，手把手教学，从入门到精通，让你： ——**每选必赢，每投必中**，快速实现财富自由，富甲一方！ 今天我们来到的地点是——**卡西米尔骑士锦标赛**。 本次的赛事有点不同，首先， $N$ 位骑士将自行组成","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10523"},"statements":[{"statement_type":"Markdown","content":"女士们，先生们。\n\n早上好，中午好，以及晚上好。\n\n欢迎来到“好得不能再好了！泰拉大师投资课”，我是你们的坎老师。\n\n不要 10000，不要 5000，只需要 999 源石锭，一对一指导，手把手教学，从入门到精通，让你：\n\n——**每选必赢，每投必中**，快速实现财富自由，富甲一方！\n\n今天我们来到的地点是——**卡西米尔骑士锦标赛**。\n\n本次的赛事有点不同，首先， $N$ 位骑士将自行组成骑士团，其中第 $i$ 号骑士将进入第 $a_i$ 号骑士团；\n\n然后接下来的 $M$ 天里，每天将指定两个不同的骑士团 $x$ 和 $y$ ，接下来每一位 $x$ 骑士团里的成员都和每一位 $y$ 骑士团里的成员进行一次比试。\n\n我们每一次比试将会下注，如果两位骑士的编号分别为 $a$ 和 $b$，那么如果你下注成功了，你将获得你的本金和 $a\\times b$ 的源石锭。\n\n当然了，每次下注你需要压上你的**所有本金**！\n\n那么请问，接下来的 $M$ 天里，在我的指导下你每天分别可以获得多少源石锭？\n\n**数据保证答案不超过 64 位有符号整型能表达的范围。**\n\n**赌博有风险，投资需谨慎！**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/gof3mumx.png)\n\n## Input\n\n输入第一行两个正整数 $N$ ($1\\le N \\le 2\\times 10^5$) 和 $M$ ($1\\le M \\le 2\\times 10^5$)，由空格隔开。\n\n接下来一行有 $N$ 个由空格隔开的正整数 $a_i$ ($1\\le a_i \\le 1\\times 10^6$) ，表示编号为 $i$ 的骑士所在的骑士团的编号。\n\n接下来 $M$ 行，每行两个由空格隔开的正整数 $x_i,y_i$ ($x_i \\neq y_i$)，保证 $x_i,y_i$ 出现在 $a_1 \\sim a_n$ 中。\n\n## Output\n\n输出共 $M$ 行，每行一个正整数，第 $i$ 行表示第 $i$ 天可以获得的最大收益。\n\n**数据保证答案不超过 64 位有符号整型能表达的范围。**\n\n[samples]\n\n## Note\n\n骑士团 $1$ 的成员有 $\\{1,2,9\\}$，骑士团 $2$ 的成员有 $\\{3,4,8\\}$，骑士团 $3$ 的成员有 $\\{5,6,7\\}$。\n\n第一天，骑士团 $1$ 和骑士团 $2$ 进行比赛。\n\n获得的收益为：$1\\times 3+1\\times 4+1\\times 8+2\\times 3+2\\times 4+2\\times 8+9\\times 3+9\\times 4+9\\times 8=180$。\n\n第二天，骑士团 $2$ 和骑士团 $3$ 进行比赛。\n\n获得的收益为：$3\\times 5+3\\times 6+3\\times 7+4\\times 5+4\\times 6+4\\times 7+8\\times 5+8\\times 6+8\\times 7=270$。\n\n第三天，骑士团 $1$ 和骑士团 $3$ 进行比赛。\n\n获得的收益为：$1\\times 5+1\\times 6+1\\times 7+2\\times 5+2\\times 6+2\\times 7+9\\times 5+9\\times 6+9\\times 7=216$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10523","tags":["2024","O2优化","高校校赛"],"sample_group":[["9 3\n1 1 2 2 3 3 3 2 1\n1 2\n2 3\n3 1\n","180\n270\n216\n"]],"created_at":"2026-03-03 11:09:25"}}