空间复杂度

乱打字讨论区

> 在这条帖子下，你来乱打字，我来解释你打的是什么意思 由于乱打字的人实在太多，我可能不能一个一个回复，没回到的可以再等等。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 666上榜一了这都能上榜

一眼望去看不到ACGO的未来

你GO严重糖分超标，除去少部分正常人无人类 我去我去，一个假AC君骂我，傻福aytx不了解事情的起因经过，开始来骂我全家装正义（唐哭了唐哭了）（（（ 这是xxs先骂我的证据 ACGO一堆唐诗，风气有洛谷一半都能成为全国知名网站了 注：本文人物均为米国字母哥，请勿对号入座

天梯能力怎么弄到100%啊？

防偷窥 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 目标是CSP-J天梯能力怎么弄到100%啊？ 我天梯40层都到了 为什么只能48% 除非目标是GESP 一级： 好多人问为什么我要攒这么多罐头，因为在13团暑期竞赛(邀请码:8554,有奖) 和 “巴威”台风专辑竞赛（邀请码：XXX2）中AK奖是送空白团队，我怕送不起 更希望有人参加，目前“巴威”台风专辑竞赛（邀请码：XXX2）只有97人报名😭， ACGO之星话题#1 依旧团贩子二人 “巴威”台风专辑竞赛（邀请码：XXX2） ACGO隐藏内容

依旧是florr的问题

身为刚入坑几天的新手，如今也是在我的不懈努力下有了这个青玻璃， so 我又来请教各位大佬，那个玻璃轮到底是怎么弄？到怎么个程度可以了？ 还是献祭自己图片：

MMOI Round 2 题解

T1 追忆 显然当 n≤mn\le mn≤m 时，需要 kkk 分钟才能将每一面都煎一遍；否则答案总是 ⌈nkm⌉\left\lceil\dfrac{nk}{m}\right\rceil⌈mnk ⌉。由于所有饼一共有 nknknk 面，至少需要这么长时间才可能能煎完所有饼；又因为 n>mn>mn>m，按照 1,2,3,…,n,1,2,3,…,n,…1,2,3,\dots,n,1,2,3,\dots,n,\dots1,2,3,…,n,1,2,3,…,n,… 的顺序每次取 mmm 个饼煎一次不可能取到重复的饼，且恰好能在这么长时间内煎完所有饼，我们证明了这个结论。 T2 无限水 可以发现新的格子变成水源后水域的周长不会变大，因此需要放置的冰块数下界为 ⌈n+m2⌉\left\lceil\dfrac{n+m}{2}\right\rceil⌈2n+m ⌉。下面给出一种能取到下界的构造： * 若 n,mn,mn,m 不都是偶数，放第一行的 1,3,5,7,…1,3,5,7,\dots1,3,5,7,… 列和第一列的 3,5,7,…3,5,7,\dots3,5,7,… 行，若 nnn 是偶数，额外放 (n,1)(n,1)(n,1)；若 mmm 是偶数，额外放 (1,m)(1,m)(1,m)。 * 若 n,mn,mn,m 都是偶数，放第一行的 1,3,5,…,m−11,3,5,\dots,m-11,3,5,…,m−1 列和最后一列的 2,4,6,⋯ ,n−22,4,6,\cdots,n-22,4,6,⋯,n−2 行，以及左下角 (n,1)(n,1)(n,1)。 容易证明这样的构造符合条件并且放置了恰好 ⌈n+m2⌉\lceil\frac{n+m}{2}\rceil⌈2n+m ⌉ 个冰块。 T3 无处存储 在输入时求出所有数的异或和 SSS，以及所有二进制下第 iii 位为 111 的数的异或和 SiS_iSi 。aaa 中出现两次的数在 SSS 中会被抵消，所以 S=x⊕yS=x\oplus yS=x⊕y。 又因为 x≠yx\not=yx=y，所以 S≠0S\not=0S=0。设 SSS 在二进制下的第 kkk 位为 111，则 x,yx,yx,y 在第 kkk 位分别为 0,10,10,1，只有一个数被计入 SkS_kSk ，所以两个数分别为 SkS_kSk 和 S⊕SkS\oplus S_kS⊕Sk ，按照大小顺序输出即可，空间复杂度 O(log⁡ai)O(\log a_i)O(logai )。 T4 攀登 使用并查集维护每个数所在的可重集，并对每个可重集维护包含可重集内所有大于 111 的数组成的链表 CCC、值为 000 的数的个数 AAA、值为 111 的数的个数 BBB 和可重集内所有数的和 SSS。 合并两个可重集 x,yx,yx,y 时，将两个链表 Cx,CyC_x,C_yCx ,Cy 合并得到新的 CCC，同时 A←Ax+AyA\leftarrow A_x+A_yA←Ax +Ay ，B←Bx+ByB\leftarrow B_x+B_yB←Bx +By ，S←Sx+SyS\leftarrow S_x+S_yS←Sx +Sy 。 对一个可重集 xxx 进行操作时，很容易计算不在链表中的数的贡献，若 v=0v=0v=0 则 A←AxA\leftarrow A_xA←Ax ，B←BxB\leftarrow B_xB←Bx ；若 v=1v=1v=1 则 A←BxA\leftarrow B_xA←Bx ，B←AxB\leftarrow A_xB←Ax 。对于链表中的数，我们直接暴力枚举每个数进行修改，若修改后小于等于 111 则从链表中删除并计入对 B,CB,CB,C 的贡献。 不难发现一个数 xxx 在进行 O(log⁡log⁡x)O(\log\log x)O(loglogx) 次操作后就会变成 000 或 111，因此每个数只会被链表暴力枚举到 O(log⁡log⁡ai)O(\log\log a_i)O(loglogai ) 次，总时间复杂度 O(nlog⁡log⁡ai+q)O(n\log\log a_i+q)O(nloglogai +q)。

心向星光，脚踩热浪，期末考试，顶峰相见！

引入 众所周知，在三个月前，我因为看到有很多人写的 CSP\mathtt{CSP}CSP 等考试的游记，就写了一篇期中考试游记（火了）。后来我又多次发布期末考试游记的预告。这次期末考试的游记，来啦！ 背景 众所不一定知，俺是一个初一的学生，在 2026 年 6 月 30 日和 7 月 1 日参加了为期两天的期末考试，本次考试为全区三十八校联考（较难），日程如下： 6 月 30 日 7 月 1 日 语文 数学 生物 政治 历史 英语 地理 暑假安全班会 再回顾一下历史战绩（呜呜期中考试生物考糊了） 为直观对比，分数全部都转化为 120 满分制，名次采用相反值 还行，其实能看，但主包作为班长+中队长（全级部 19 个班只有 6 个班长同时担任中队长，按理来说成绩应该更好），成绩在所有中队长里面比较靠下，还需要努力。 考前分析 第一场语文最好考好了，不然就会出现上次语文考太差影响政治的情况。英语排在最后其实对我不利因为前面考试对最后一场的心态影响极大。生物政治得好好考不然优势科目（英语&历史&地理）优势会减弱。All in all , 加油吧。 考前复习 着重复习的政治和生物，其他咋看。 考前状态 拉完了……感冒 + 有“点”哮喘 + 咳嗽 第一天 语文 8:00~10:00 哇塞🤩，监考老师这么良心 7:567:567:56 就发卷了，一共有 888 面。帅气聪明的我仅仅用了 111 分钟写完了基础选择👍（共 444 题），又用了 444 分钟写完了古诗默写（共 101010 空），距离正式开考仅过去了 111 分钟！ 到了第 7 题，我有点不会……它让选择错误的一项 but 我感觉都对了（但至少不是都错了），我就想起来了一个班梗：Zoe 问 Julian （通过真名发音让 AI 拟的化名）一个数学证明题，Julian 想都没想直接说：“选 C ”于是我决定第 7 题选 C 🤣 第 7 题一个小选择浪费了我 3 分钟但不要紧时间还有很多，接下来我有用了 444 分钟写完了第 8 题古诗赏析。但是，我没涂到答题卡上！我不知道还在继续做名著阅读的选择和赏析。本身名著阅读就比较难选择加赏析一共俩空浪费我 666 分钟，然后我不知怎地，居然把名著赏析写古诗赏析上了呜呜呜呜，写的满满当当，写完后才发现😭，痛失 333 分！ 我直接开狂暴，秒切文言文阅读，用 999 分钟做完俩文言文选择+文言文断句+俩文言文翻译，此时时间已经来到 8:238:238:23 ，我已经做完了 3.53.53.5 面局势一篇美好。⛰️ 文言文哲理题发现我没弄懂直接过，开始涂前面的卡，等涂完卡再写完这个哲理题发现 8:518:518:51 了瞬间老实了。 202020 分钟过后，我把第一篇现代文阅读《戈壁花开》做完了，写的满满当当的应该没问题✌️ 又用了 282828 分钟做完第二篇阅读，写的更🈵（bushi） 我差点没写完作文，感觉写的一般，描写比较少但生华直接对标梵蒂冈教宗发言稿，但不敢写为党和人民做贡献了因为上次这么写说是涉政扣了 101010 分呜呜呜…… 以上内容为 2026 年 7 月 2 日编写，编写进度不足 15% 居然上榜了 生物 10:20~11:20 监考老师依旧大发慈悲 10:1610:1610:16 就发卷了，时间一共有 121212 面。 然后 (Ta's Ma)'s 居然严禁我们作答，还说这是抢答。我没办法就等他们说完在看题的时候把答案记在脑子里一会儿写上去。 一打铃，我立刻把我做的四个选择题写了上去。第 555 题挺难的我看了好长时间，（转折点）结果突发恶疾，哮喘不断。我也不敢老咳出声音来（学校有规定考试如果突发哮喘多次持续发出噪音，考生一律到厕所，不得过多影响考试纪律，监考老师必须同意）就打报告去厕所了。然后就是一直咳嗽感觉都喘不上气了温馨提示：我还活着 回来一看 10:3510:3510:35 了，赶紧写，在 10:5810:5810:58 写完了选择题（一共 777 面仅耗时 171717 分钟） 31 题又是一个难题（大题），里面的一个小问有点猎奇： 移栽幼苗：移栽时要带土坨，目的是（保护幼根和根毛），尽量选择阴雨天或傍晚移栽成活率高，蕴含的生物学原理是（） 第二个空我懵了，我记得生物老师过我们什么只要看到...就写“功能与结构相适应”，可是这填进去对吗？！ 我选择相信自己，填进去了（bushi） 写完一看就剩 999 分钟收卷了，我直接炸了💥 （OS：到现在就算全对才 404040 分，更何况我前面半蒙半写） 最后 999 分钟我狂写 4 面大题，还剩一面，当场力竭…… 历史 正在写…… 结尾 未完待续……

黑客之都暑期每日训练赛

¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿¿ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我团开启每日暑期的训练赛，所有比赛将由当日开始当日结束，所有比赛报名为当日早晨0:00到次日0:00，比赛时间为早晨7：00到次日7:00；所有题目来源于官方题库（有些比赛有特殊情况会进行寿命！！！） 赛事目录： * 1.-7.7比赛（基础算法，模拟）邀请码：ykGG * 2-7.8比赛(基础算法，枚举）邀请码：c6WT * 3-7.9比赛(基础算法，递归）邀请码：E8mB * 4-7.10比赛(基础算法，贪心）邀请码：bp23 * 5-7.11比赛(基础算法，递推）邀请码：SkMe * 6-7.12比赛(基础算法，分治）邀请码：iF5B * 7-7.13至7.18比赛(基础算法，上述内容综合题目，时间调整为5天，原创题）邀请码：JmSe

二分笔记

1. 查找 X 是否存在 思路简介 数组有序时，可以用二分查找。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 手写 LOWER_BOUND：查找第一个 >= X 的位置 思路简介 要找的是第一个满足： 的位置。 二分时，如果： 说明 mid 可能是答案，但是前面可能还有更靠左的答案，所以： 如果： 说明 mid 和左边都太小了，所以往右找： 如果不存在，输出 n + 1。 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. STL LOWER_BOUND：第一个 >= X 思路简介 lower_bound 的含义是： 写法： 返回的是地址。 要转成下标，需要减去数组首地址： 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. STL UPPER_BOUND：第一个 > X 思路简介 upper_bound 的含义是： 写法： 返回的是地址。 转成下标： 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5. 手写 UPPER_BOUND：查找第一个 > X 的位置 思路简介 要找的是第一个满足： 的位置。 二分时，如果： 说明 mid 可能是答案，但是前面可能还有更靠左的答案，所以： 如果： 说明 mid 和左边都不满足，只能往右找： 如果不存在，输出 n + 1。 带注释代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结口诀 这几份代码的前提都是：数组必须是有序的。如果题目没保证有序，需要先写： 出现次数2 保龄球 出现次数1 和为 0 的 4 个值 最后一个等于X的元素 不同分的人数 学生信息查询 A-B数对 递增三元组 放学人潮

【获奖公告】挑战赛#33

🎁 挑战赛#33 获奖名单 🏆 获奖名单 排名获奖 用户ID 用户昵称 名次 奖励 5498487 @xiao7Mr10 2 拼图X1 +盲盒X1+1500罐头 4740693 @AAA_Cheer_EndBet 3 拼图X1 +盲盒X1+600罐头 5096117 @清风逸客 4 拼图X1 +盲盒X1+600罐头 5246373 @‮🐱‍🚀（互关来） 7 拼图X1 +盲盒X1+600罐头 5205535 @樱花入梦 8 拼图X1 +盲盒X1+600罐头 5243039 @Light.cpp 10 拼图X1 +盲盒X1+300罐头 5091553 @qwqaq 11 拼图X1 +盲盒X1+300罐头 2901632 @༺ཌༀ复仇者.凤凰.浅琪ༀད༻ 12 拼图X1 +盲盒X1+300罐头 5141353 @互关·守城的HKP 13 拼图X1 +盲盒X1+300罐头 4156430 @MuktorFM 14 拼图X1 +盲盒X1+300罐头 4913788 @万泉不是入 15 拼图X1 +盲盒X1+300罐头 3411835 @昭宁（泠松月）🤪 17 拼图X1 +盲盒X1+300罐头 4790834 @异雷 21 拼图X1 +盲盒X1+300罐头 494973 @不会C++的一只屑生姜 22 拼图X1 +盲盒X1+300罐头 4502537 @M28 25 拼图X1 +盲盒X1+300罐头 幸运奖 用户ID 用户昵称 奖励 5471132 @小小刚 100罐头币 5623502 @༺ཌༀ推时透·互关ༀད༻ 100罐头币 3874216 @粉丝破200我吃💩 100罐头币 4777160 @edition_Ant-- 100罐头币 1415209 @Hi renji 100罐头币 4955978 @༺ཌༀཉི༒白·羊༒༃ༀད༻ 100罐头币 5037597 @CH---陈(必回关) 100罐头币 5706956 @༺ཌༀཉི༒喵__呜__喵༒༃ༀ 100罐头币 4680508 @小柏 100罐头币 5395070 @莫子杰 100罐头币 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 前100名违规名单 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 【45】名用户存在违规或疑似AI生成或高相似度代码的情况。 公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 违规人员名单 用户ID 用户昵称 5712389 @孙睿阳（互关） 4533948 @Khalil 5084286 @《三分之一是仍需调试》 4946548 @ye >^< ━╋══⁕═➢ 4690036 @喵仔牛奶 5498557 @186****7687 5579954 @我是黑奴 1899831 @永盼 2369824 @王志强 3144290 @晚叙꧁一捧皎洁玥光 4976800 @哪吒之魔童降世 5185108 @【典狱长】格赫罗斯 5491220 @wurendexianian 4714594 @丁瑞宸 5581724 @༺ཌༀཉི 我的世界 ༃ༀད༻ 5707272 @great 5722418 @蒋致远 5725376 @三角洲行动 316363 @李昊宇 4497569 @神 5569151 @『彳 亍』 4261397 @泪眸 5545814 @死神永生 4644662 @༺དༀ༒۞神&威龙۞༒ༀཌ༻ 5508483 @青屿见 745526 @F0rsaken 5491733 @. 4710712 @꧁༺ཌༀ善ༀད༻꧂ 4976685 @消失的AC 无尽的RE 3487655 @姌额 5085886 @李君廷 4635864 @阳泽诚 4723741 @北岸初晴 5205782 [@Deep欠揍 1776467 @浩浩超甜 4104093 @༺ཌༀ༒∞神.精英∞༒ༀད 2556825 @WTL 5301244 @user_5301244 徐天骐 5279318 @先发滋人 5725346 @邓智森 4647636 @凤凰-青得偏红 3674612 @༺ཌༀཉི༒威风·的龙༒༃ༀད༻ 2018805 @༺ཌ༒ཌༀཉ王腾大帝༃ༀདད༻ 4605744 @༺ཌༀGTI指挥官ༀད༻ 5469308 @睿 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 申诉机制 请在【2026-07-12】前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。如果提交申诉后，依旧被判为违规，则禁言7天以示警告。 本轮赛事审核 @NoonMaple 📎 ACGO 官方赛事公平审核规则 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，统一 禁言 30 天； * 仅违规 1 次者不予展示。 本场赛事违规且累计≥3（挑战赛#33） 用户ID 用户昵称 累计违规次数 4976685 @消失的AC 无尽的RE 6 5491733 @. 6 2556825 @WTL 5 4976800 @哪吒之魔童降世 5 4690036 @喵仔牛奶 4 5205782 [@Deep欠揍 深度欠揍](/person/5205782) 5279318 @先发滋人 4 5508483 @青屿见 4 316363 @李昊宇 3 4533948 @Khalil 3 5581724 @༺ཌༀཉི 我的世界 ༃ༀད༻ 3

MMOI Round 2 题目总结

前言 & 闲话 比赛质量还行，但是出了很多搞笑的状况，比如 T3 的空间莫名其妙变成了 2048MB，大概是4点多吧，反正我打的时候准备看 T3 的时候来了个提示说 T3 空间限制修改了。 莫名其妙，而且有一个比较好玩的情节。 不会重复提及某题题意，请自行观看。 T1 红，没什么好说的，注意一张饼需要操作 kkk 次，同时有 nknknk 面需要操作，答案就是 max⁡(k,⌈nkm⌉)\max (k,\lceil \frac{nk}{m}\rceil)max(k,⌈mnk ⌉)。 懒得给代码。 T2 构造可能有点创人，但是我觉得还好。这个扩展有一个特性：加入一个格子水域周长不会增多。原因很显然，因为规则中指出格子四联通周围有两格及以上才会扩展，一个格子就四边。最好的情况相当于有两面接壤，然后有两面补上了原来接壤的那个空缺，周长不变。 然后我们发现最终状态整个网格都被填满，水域边长为 2nm2nm2nm。也就是说答案的下界一定是 ⌈n+m2⌉\lceil \frac{n+m}{2} \rceil⌈2n+m ⌉，相当于一个格子周长为 444。下界也不难得到，构造如下： * 在左上角 2×22 \times 22×2 上方的 (1,2)(1,2)(1,2) 和 (2,1)(2,1)(2,1) 放水，把这块区域填满。（出题人巧思不错，这就是 MC 里面无限水的做法） * 然后我们发现可以隔着两个放一桶，比如填满列就填充 (1,4),(1,6),(1,8).....(1,4),(1,6),(1,8).....(1,4),(1,6),(1,8).....，这样我们可以让第一行都被填满，第一列同理。 * 然后我们发现此时整个过程相当于说逐渐从边缘扩展，逐步的水会扩展每个格子。 还有一些特殊情况，这样的方案无法覆盖到末短是奇数格子的情况。比如 nnn 为奇数时，格 (n,1)(n,1)(n,1) 就无法被覆盖到，此时加进去就可以了，如果 mmm 是奇数同理。需要注意的是，当 n，mn，mn，m 均为奇数时只需要填充 (n,m)(n,m)(n,m) 即可，不然会有冗余。从这里也可以看出构造是严格达到下界的。 时间复杂度 O(nm)O(nm)O(nm)，总体而言还行。 这是这位同学你 @消失的AC与写不完的UKE 要的代码。 下次记得晚点发hhh。 T3 有点意思，这是一个比较新颖的题，但其实也比较简单。首先其他数出现两次这个性质启示我们想办法对这些数作区分，一个运算能很好的体现这个区分性：异或。 因为 x⊕x=0x \oplus x = 0x⊕x=0，原序列的异或和就是要求的那两个数 x,yx,yx,y 的异或值 sum=x⊕ysum=x \oplus ysum=x⊕y。并且我们发现 sumsumsum 至少有一位非零，因为 x<yx<yx<y。然后此刻某一位为 111 的意思就是这两个数二进制下这一位不同，随便找到一个为 111 的位，如果 d=2d=2d=2 针对这一位为 111 的再做异或就可以得到 x,yx,yx,y 的某一个，然后再和 sumsumsum 异或一次就得到两组解了。 到正解其实和 d=2d=2d=2 没什么区别，二进制位一共就 log⁡V=60\log V = 60logV=60 位左右，每次读入的时候开一个大小为 606060 的数组 pip_ipi 表示第 iii 位为 111 的所有数的异或和，然后直接查表就可以了。 时间复杂度 O(nlog⁡V)O(n \log V)O(nlogV)，空间复杂度 O(log⁡V)O(\log V)O(logV)。当时是写了个模拟过的（2G空间），后面觉得有点不地道然后写了个正解，反正场上两种都过了。 T4 思考了 10 分钟，有一个细节有点意思，其他没什么难度。 首先一个经典的观察是每个数最多经历过 log⁡log⁡V\log \log VloglogV 次开根操作就变成 111 了，所以这一部分是可以对每个数暴力做的。然后观察数变成 111 后的特殊性质： * 如果目前操作是 +1+1+1，那开根后向下取整还是 111。 * 如果目前操作是 −1-1−1，那直接就是 000。 同时，000 怎么操作都一定会变成 111，所以每个数最终的归宿 000 或 111 可以批量维护，我们只在意个数。如果操作是 +1+1+1 就没影响，否则就交换 000 和 111 的个数。查询就是 111 的个数加上其他数的和。 重点是合并操作，由于这个 nnn 太大了不能直接启发式合并，但其实有一个很聪明的方法规避暴力合并：使用链表维护所有大于 111 的数，再做合并。（开头提到的有点意思的点） 链表合并的方式很简单，记录链表的头指针和尾指针，合并时把一边的尾指针的后继改成一边的头指针就行了。这个过程时间复杂度是 O(1)O(1)O(1) 的，然后很经典的用并查集维护集合。 处理开根操作的时候遍历链表，每个数暴力处理，更新总和并且看看操作后能否规约到 0/10/10/1。这一点可以使用两个变量维护头指针和尾指针，具体实现看代码，没什么好说的。 开根反而是时限瓶颈，这里卡常使用了一个值域分治技巧，如果数 ≤107\le 10^7≤107 查表即可，这一点可以简单预处理。默认开根为 O(1)O(1)O(1) 则总时间复杂度为 O(nlog⁡log⁡V+qα(n))O(n \log \log V+q\alpha(n))O(nloglogV+qα(n))。