第k小整数题解

【天梯闯关】保卫战正式打响

> AC军团们注意！🚨 你们期待的「天梯闯关」新副本已加载完毕！ 🎯 全新玩法亮点抢先看： ✅ 剧情式闯关体验 - 专属剧情导入，沉浸感拉满 ✅ 渐进式关卡挑战 - 从第一关开始攀登，层层解锁 ✅ 实时代码竞技场 - 禁用复制粘贴，纯手写代码见真章 ✅ 智能奖励系统 - 通关即获金币，失败推荐专属题单 🕹 闯关须知： * 必须登录才能进入天梯系统 * 严格关卡顺序，必须先通关前一关 * 每关限时挑战，代码需现场手写 * 通关条件：每关所有题目全部AC！ 💎 闯关奖励： * 每关通关即得金币奖励 * 登顶天梯榜的玩家将获得限定成就 * 失败也不怕，系统智能推荐提升题单 据说能登顶的都是能手撕算法、脚踩异常的真·大佬！你的头发和AC率都在等你拯救！ ❓ 最新情报： > 1. 第二关 Happy Birthday! 样例无误； > 2. 第三关《奇妙的数字变化》 10.22 已更新； > 3. 通关获得的罐头，之后可以兑换社区商城（待上线）的物品哦； 👉 【立即挑战】：天梯入口 💬 互动话题： 1. 你觉得自己能冲到第几关？ 2. 最期待在天梯中遇到什么类型的题目？ 3. 来预测下谁会是第一个登顶的AC大神？ 4. 闯关截图合影留念！ 🎁🎁🎁 在评论区留下你的闯关宣言，随机抽3位幸运鹅送出ACGO拼图冰箱贴！10月31日公布获奖！

【互动】#1024吐槽节#

💥 #1024吐槽节# 盛大开幕！ 嘿，AC狗友们！🧑‍💻 又到了一年一度，咱们程序员的专属节日——1024！ （没错，ACGO也有自己的小传统了，仪式感拉满 😎） 所以，我们决定如期举办那个 “让人又爱又恨” 的活动—— #1024吐槽节# 今年的规则，简单到令人发指： > 看ACGO哪里不顺眼？大胆开麦！ 是题库太阴间？测评机日常抽风？ 还是社区功能用起来像在考古？ 或者，你单纯想对我们AC君喊一句： “你们这个功能是祖传的吗？能不能动一动！” 没问题！今天你说了算！🫡 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 来来来，指条明路（欢迎自由发挥）： * 「功能篇」：题库、测评机、排行榜、编辑器… 哪个让你血压飙升？ * 「社区篇」：氛围、活动、推荐机制… 哪里让你想“原地退站”？ * 「运营篇」：希望我们多整活？多发福利？还是… 少整点烂活？🤣 一句话：今天我们不开夸夸团，专心 “Debug ACGO”。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 参与姿势： 1️⃣ 带话题 #1024吐槽节# 发帖或直接评论本帖 2️⃣ 尽情输出你的“血泪体验” + 你心目中的完美改进方案 3️⃣ 支持各种形式：小作文、段子、表情包、灵魂拷问… 越真实，越有力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 而我们，郑重承诺： * 所有高赞、走心的吐槽，我们保证逐字阅读，跪着回复！ * 那些闪闪发光的金点子，将直接进入 「ACGO优化清单」 （是真的会排期的那种！） * 被我们“盯上”的优秀吐槽官，还会收获一份 “忍住别哭” 的小惊喜 🎁 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 活动礼品： 高赞奖：点赞最高的前三位，送上ACGO钥匙扣盲盒 金点子奖 ：我们将选2-5名，送上AK吧唧 优秀吐槽官奖 ：我们将选选2-5名，送上ACGO周边定制笔 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🗓 活动时间：10月14日 至 10月26日 💬 活动主旨：吐槽是门手艺，进步需要勇气。 毕竟—— ACGO的bug或许会迟到，但我们想修好它的心，永不缺席！ 🛠️ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

【新周边】把AC狗“贴”上冰箱！

> 限量版「ACGO拼图冰箱贴」已登陆，让你的每一次AC都触手可及！ 亲爱的AC狗友们，注意啦！📣 你们催更的赛事实物奖励，这次真的来大的了！ 从本月底起，除了积分与荣耀，你刷过的题、熬过的夜、AC的代码，都将化身为可以亲手触摸、自由拼贴的实体成就——ACGO拼图冰箱贴限量登场！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ✨ 精雕细琢，只为珍藏你的每一次AC 🧩 12块碎片，记录你从萌新到大佬的成长相册，更是只属于ACGO Oler的硬核勋章墙。4大高光阶段，精准对应你的信奥成长轨迹： 🐶 AC狗拼图规格：完整狗拼图高度约为20厘米，适合贴在冰箱或磁力墙上。 🎨 高透精雕亚克力：采用高品质亚克力材质，通过精密雕刻与全彩印刷，画面清晰锐利。 📦 单片独立封装：每一块拼图碎片，都拥有自己独立的专属包装袋。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎮 三大获取路径，总有一条适合你 获取方式 拼图来源 🏆 打比赛挣 • 全系列赛事覆盖！• 名次越高，拿得越多• 巅峰赛必掉稀有「巅峰王者」碎片！ 🎁 抽奖试试手气 • 每场赛事都有“幸运抽奖环节！• 名次不够？欧气来凑！ 🛒 商城直接补（待上线） • ACGO商城提供精准补给！• 缺哪块，买哪块，秒速完成收藏！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🏅 终极彩蛋：解锁「拼图大师」专属勋章！ 当最后一块拼图“咔嗒”归位，12块碎片完整合体—— 请务必、立刻、马上去ACGO社区晒出你的完成品！ 我们将为你解锁专属「拼图大师」荣誉勋章，永久点亮你的个人主页，向所有人宣告你的毅力与实力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 拿下你的第一块拼图 🌟 现在，就从本次欢乐赛#59开始，拿下你的第一块拼图吧👉 立即参赛 🌟 10月20日至10月31日，互动区留言互动，抽取5位幸运鹅送拼图碎片！

远征·永夜孤光(1)

> 第一章·光影(1) 一个小小的水洼里的一条鱼，它努力地向外跳，努力寻找新的水源，在黑暗的夜里寻找着，它跳上了干燥的马路，鳞片在昏黄的灯光下闪着白光。它相信他一定能找到水源，前面确实干燥的马路，像宇宙一样广袤无边……它艰难地呼吸着，暗黑的夜中时间仿佛停止了，它用最后一丝力气再跳一次，没有到达水洼，它最后一次仰望星空，看到美丽而灿烂的星空，一颗颗星闪烁着，用它们的躯体燃烧着生命……小小水洼里的一条鱼满意地闭上了眼睛，它不再渴望水洼，它渴望灵魂永远在无边的宇宙中翱翔…… 林尽是个十几岁的少年，他在回家的路上走着，他捡起了那条鱼，看着这早已没有生命的躯体在昏黄的路灯下闪着银光，他慢慢地吧鱼放进一个浅浅的小水洼里，抬头仰望星空：“人类渺小而脆弱，在宇宙中，它们连一粒灰尘都算不上，但是我相信，人类不会被那些毁灭的力量摧毁，人类很坚强。” 林尽继续往回家的路走着，所有路灯突然熄灭，原本在这夜晚还有一丝灯光的安慰，现在这些灯光化作了一缕烟云，消失在着无边的黑夜里……他感觉整个世界都暗了下来，唯独天上的北极星是给他指路的灯塔。 林尽再次抬头仰望星空，他好像看到在这个黑暗的夜突然显出一种红色，像是宇宙的伤疤。他不敢相信，他认为自己产生了幻觉。可是再次抬眼一看，在这个红色裂口中伸出一个像龙卷风一样长长的光束。他很害怕，他努力地向佳的方向跑去，无边的暗夜下起了雨，像是晶莹的泪打在他身上。天上，这一束光快速地向地上伸展，层层光束中伸出一个长长的圆柱体，正向林尽家的方向深去…… 天空流着蓝白色的血，这黑暗而宁静的夜变成了恐怖主义者思想中的残夜。此刻，是林尽人生中凄冷的黑夜，他望着家，那乌黑的圆柱体正在将他的家毁灭！一片片细小的碎片随着残存的风轻轻扬起，飞到了无光的角落……“不！我的爹和娘！”他用尽力气叫喊着，好似在这天底下只有他一人在哀嚎…… 天上残存的星云不再漂浮，地上的花儿也不再开放。他看到了他的家人：他们正被吸附在圆柱体上向悲凉的宇宙伸去！他们叫喊着，希望微弱的声音刺破黑暗，给一段悲惨的童话画上一个句号。他拼命奔跑着，像家的方向奔去，他希望那片原属于家的土地能带给他意思安慰。 星云中的恒星继续燃烧自己的生命发出光芒，宇宙的运行依然依旧。林尽说他很爱宇宙，他喜欢一颗颗灿烂的恒星，他喜欢极致的浪漫发出的无边的美。可是他不再仰望星空，因为他知道这些星云能孕育出恐怖的野兽，它们发出的低吼奏响了宇宙级的安眠曲…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 目录 > > > 好心人加一下他的团队

《AC之前的往事》1

其实是不想搞这个的 但是有点难过 所以想找朋友们谈谈心 第一个 我想和大家说说"我" 姓名：小冰果（不想说真实姓名） 年龄：13 小学：不说了 中学：海淀外国语 爱好：看《三体》 玩pvz 玩英勇之地 做c++ 一开始 我是一个XMW学员 我的任务就是学好c++ 让家长放心 接触了ACGO 发现了一个"能让我活下去"的地方 5年级的时候 孤僻离群 没朋友 还被校园80 特别喜欢编程课 觉得很开心 认识了@魏敬平这个入 当时有了一个朋友 5下因为被80转学了 不在乎 认识了陈匡则，罗希，王乐威这几个朋友 其实没什么 就是顺带提一笔 主要的事还是后面ACGO的事 第二部分 来到了ACGO 是一个无名小辈 大部分认识的都是小马王集训营 类似的@听取WA声一片（C1103）@TN Hacker 还认识了一个大佬@滚蛋吧c++加入了他的团队 第一小部分是关于他的 你好 对不起打扰你了 问题1：你好厉害啊 但是没上榜 算是社交界的大佬吧 我见过你 在去集中营的班车上 没敢说 看起来你很普通 去集训营后 你又表现得很厉害 对比当时的我 其实很绝望 你肯定没注意到我 我是班里的小透明 好像扯远了 自己理解吧 这里面藏了个问题 离开这里 去你想去的未来 第二小部分 @༺ཌༀ我要上南开ༀད༻ 她才6年级 却比我这个初中生做的更好 她的6年级内卷日记很火 写出了悲欢离合 却没有绝望 可我不一样 总是闲着 想紫砂 陈匡则没有错 只是说出了我的内心 对不起大家 我骗了你们 你们都很开心 我只是一个死了没人管 活着没贡献的人 我很崇拜她 可我论辈分比她大 这没什么错 放手去做 不要管我 第三小部分 @张静之 你是一个同样爱玩游戏的人 也是一个同样优秀的人 我不如你 我只是一个在ACGO出题发布内心想法的人 只能靠游戏麻痹自己 哈哈哈哈哈哈哈哈呜呜呜呜 在我心里你很重要 可是我在你心里可能只能算个过客吧 我中了！我中了！我中了！！！！ 第三部分 问题 也是问大家 你么觉得我是什么B东西 随便骂我吧 发泄你们的想法 谢谢大家 以后会更新的！这是冰果自己发的！保真啊！ 下面是小记 @AC君@AAA混凝土批发ppl哥@一只德意志联邦球 随便找三个人 下一篇:传送门

《C++》

呃呃呃上榜一换头像 主歌1 cin的尖刺永远朝外 却是最重要的代码 cout把所有伤害留给自己 却总会有人忘了加 cin对变量严刑掏问 却从未知道输入的值 cout刀尖只指向自己 变量才把值递给它 预副歌1 iostream明明尽力去实现 却做不到字符串 万能头一出场即是万能 功能千千万 副歌1 main是最重要且唯一的函数 其他函数则是创建就注定了参数 递归从未停下return的脚步 却还是被break带入了迷途 引用渴望变量的庇护 却被野指针引上不归路 for循环遍历揭开了迷雾 却不知如何输入 预副歌2 指针总在内存里流浪 找不到正确的家 数组把元素整齐列队 却逃不过越界的惩罚 副歌2 main是最重要且唯一的函数 其他函数则是创建就注定了参数 递归从未停下return的脚步 却还是被break带入了迷途 引用渴望变量的庇护 却被野指针引上不归路 for循环遍历揭开了迷雾 却不知如何输入 桥段 int不敢计算高精度 double又要格式化输出 char不能用cin输入 string头文件却总是迷路 副歌3 main是最重要且唯一的函数 其他函数却是创建早已注定参数 递归从来没停下return的脚步 最终却被break带入了迷途 引用多渴望变量的庇护 却被野指针引上了不归路 for循环遍历揭开了迷雾 却未知循环次数 尾声 深搜执着向前的路 广搜代码很好读 冒泡选择的梦是正确快速 sort的下标却总是糊涂 for循环遍历揭开迷雾 未知循环次数

远征目录

> 永夜孤光 第一章·光影

我天梯赛30层了，ACGO第一入😋😋

AC君快给我奖励！！！ 我其他什么都可以不要，只求一个限定的徽章。。。 @AC君 最后一层的“翻转求和和”有问题，具体是数据问题还是题目问题我也不知道，反正就是有问题，不过现在已经改了（（（ > 为什么说我可能是第一人？ 我和管理员沟通发现，之前的几个人大部分都是AI（管理员不想查了，所以是大部分。。。），行为非常恶劣！！！望周知！！！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ -MVP结算画面- @4911730‮ @༺ཌༀ我要上南开ༀད༻ @STARS_SEEKER @福永州泰 @DOG @‮（关回必）达仲_明孔_者仇复 @学神

《AC之外的往事2》

我叫小冰果 或者叫"合莫" 我也叫合莫 因为......我其实也忘了 但是这两个人完全不一样 所以.......... 冰果决定见一见另一个"自己" 网上说有一种叫"阳光型抑郁"的玉玉症 其实并不是这样 或是说只有冰果是这样 面对别人：高抽象 笑得特别邪恶 爱玩游戏 实际上:只敢在网上发布自己的内心想法 一直哭 他是个s13 至少对于其他人来说 但是 一天 他见到了"合莫" 我其实有精神类疾病 所以不排除是精神分裂（我有病吧） 其实他的大部分快乐都是两个灵魂一起度过的 一个悲伤阴郁 一个快乐 所以.....你们也猜到了发帖的是谁把 可以对标我的sph想看的加我v微信smq7011 谢谢大家 @༺ཌༀ我要上南开ༀད༻ 对你说的话： 谢谢你 一起加油吧 虽然我希望你和我不一样 又希望你和我一样 至少开心一些 我要过生日了 我的愿望是： 希望看我贴的所有和我一样遭遇的人都开心起来 绝望的原因是住校和80 所以 谢谢大家 广告 公告 加入这个团队 我不希望水贴上榜 但是我觉得我这么做没错 我为自己打上了一个思想钢印:只要能反80一切都是对的 @白色死神 （必回关） @张静之 我更新了哈哈哈 我ip在河北是因为我的学校在河北！！！

巅峰赛 #26 T1,T2,T5 题解

其实就是为了让我的 T5 有趣解法能进讨论区而发的（ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 * 思维：普及- * 算法：普及-（快速幂） * 模拟：入门 * 综合：普及- 好骗兄弟，好骗。 自行模拟，可以发现无论如何摆放齿轮，结果一定是合法的。 所以总情况数为 2hw2^{hw}2hw。 时间复杂度：O(log⁡p)O(\log p)O(logp)，其中 p=998244352p=998244352p=998244352。 T2 * 思维：普及- * 算法：入门/普及-（无） * 模拟：入门 * 综合：普及- 考虑贪心，先试试能不能放第一个盒子，如果可以就放，不可以再试试能不能放第二个盒子。 如果有一个数能放第一个盒子，但你把它放了第二个盒子，显然不优。 时间复杂度：O(∑n)O(\sum n)O(∑n)。 T5 * 思维：普及- * 算法：普及+/提高（树状数组，树形 DP） * 模拟：普及+/提高 * 综合：普及+/提高 好玩，以后多出这种题。 我们可以离线所有查询，然后搜索整棵树，在搜索完后合并所有子树的信息。 这样的话查询一定得在 O(log⁡n)O(\log n)O(logn) 左右，我们可以使用 map 和权值树状数组存储一个节点的信息。 map 用于记录每种颜色出现了多少次，权值树状数组用于查询出现次数小于等于 kkk 有多少种颜色。 具体实现就是这样的： 然后考虑如何合并一个点的所有子树的节点。 把子树的信息全部合并在这个点上？很显然这样子单次合并时间复杂度是 O(sizelog⁡size)O(size\log size)O(sizelogsize) 的，可以构造出一条链来将这种做法卡到 O(n2log⁡n)O(n^2\log n)O(n2logn)。 我们可以选定子树大小最大的子节点，然后把所有信息合并到它那。为什么这样是对的呢？我们可以假设当前节点子树大小为 nnn，最大子节点的子树大小为 mmm，则其它的树大小绝对不超过 mmm。则时间复杂度的函数可以如下表示： F(n)≤O((n−m)log⁡n)+nmF(m)F(n)\le O((n-m)\log n)+\frac{n}{m}F(m) F(n)≤O((n−m)logn)+mn F(m) 显然，当 mmm 与 nnn 是同一个数量级时，只需进行 O(n−m)O(n-m)O(n−m) 次合并，而递归其它子树的时间复杂度可以忽略不计，总时间复杂度约为 O(nlog⁡n)O(n\log n)O(nlogn)； 当 nnn 与 mmm 不是同一个数量级，经主定理可得时间复杂度为 O(nlog⁡2nlog⁡nmn)O(n\log_2 n\log_{\frac{n}{m}} n)O(nlog2 nlogmn n)。 所以这个做法的时间复杂度为 O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 接下来就是如何实现了。 我们可以用一个 vector 数组，当递归到叶子结点时，在 vector 里面加入一个节点，包含它这一种颜色，并返回下标；否则先递归子树大小最大的子节点，获取它返回的下标，然后将其它向下递归，将获取的下标合并至最大的子节点上，最后返回存储最大子节点的信息的点下标。 最终代码如下： 时间复杂度：O(nlog⁡2n+qlog⁡n)O(n\log^2 n+q\log n)O(nlog2n+qlogn)。