清华大学系列链接

互动｜真没招了！那些让你当场放弃的瞬间

真没招了！那些让你当场放弃的瞬间👇 Hi，AC狗友们 。有没有那么一刻 ，你对着屏幕 / 书本 / 生活 ，默默说了一句：“算了，真没招了”。 不是摆烂，是真的尽力了 。但结果还是……emmm 🎁交出你的“没招了”瞬间🧾 👉 你最近一次觉得 “真没招了” 是什么时候？ 👉 因为什么事？后来怎么解决的（还是没解决）？ 评论区直接写👇 例子：“调代码调了俩小时，结果是中文分号，真没招了。” 格式不限，一句话 or 小故事都行～ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 福利时间 活动截止后： * 评论点赞前 5 名 → 罐头 × 50 * 随机抽 5 人 → 罐头 × 20 ⏰ 即日起 至 2026 年 6月 16 日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💬 评论区交出你的 “没招了” 瞬间 往期互动

被老师请去喝茶的一天

啊？不是，上榜了？\LARGE 啊？不是，上榜了？啊？不是，上榜了？ 我真服了呀，今天竟然被老师请去办公室喝茶了😭😭(是因为我数学考了78分，一个非常吉利的数)大家有被老师请去办公室喝茶的经历吗？给我分享一下呗꒦ິ^꒦ິ

关于我在豆包上搜堵开学事件大 开 眼 界

不是怎么榜三了 不是怎么一堆刷惯投的 刷罐请点链接描述 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这是我搜豆包的图 神奇 我就想问他说的哪件事是真的？！？！？！？！ 《提议不上线、不刷题》 《刷****词语》 《用AC数量堵住开学》 不是 这个贴不是说用fu mu堵住吗？？？ 何意味没一条真的 《满屏堵开学》一小时内上千条回复倒是真的，但是其实满屏都是骂 《花似雪、几名大佬用户也发》花似雪早就退了，而且“几名大佬发”是何意味 《冲到第一盖过欢乐赛》冲到榜一倒是不假，但是欢乐赛是什么鬼，难道说神秘的欢乐赛题解百年一遇的上榜了？没有吧 还有很多地方我不想说了，主要是这鬼畜玩意能不能依据事实啊…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

六一互动｜原来我从小就是个逻辑控？

🎈六一特别企划｜不是吧！原来我从小就是个逻辑控？ hi，AC狗友们 ，不是只有写代码才叫编程🧠 小时候玩过的那些游戏/玩具 ，可能早就偷偷给你种下了 逻辑思维的种子🌱 🕹️ 看到这些DNA动了没 🥇 Scratch小猫跳一跳 👉 原来“碰到边缘就反弹”就是if语句啊喂！ 🥈 Minecraft红石电路 👉 第一次手动实现“与门”，比数学课还早 🥉 Lightbot点亮灯泡 👉 用函数调用那关，脑子直接“叮”一声通了 …… 🎁 换你了！！！ 👉 你小时候玩过哪个 游戏/玩具 让你觉得“这好像在玩逻辑”？ 👉 有没有一个瞬间，让你突然觉得“我脑子转得快是因为它”？ 评论区直接写👇 格式不限，一句话or小故事都行～ 🎁 福利时间 活动截止后：符合活动要求的评论 * 点赞前6名 → 罐头 × 60 ； @RuiDaShuai2025，@全站的狗子我嘴最臭(慕温)，@༺དༀ༒哦，那咋了༒ༀཌ༻，@💩💩百大游戏解说官💩💩，@shenzhangzheng小号，@小金 回关 * 随机抽6人 → 罐头 × 20 ；@仙布着急，@horse，@人机猫，@天之神-小天狼星·布莱克，@玩不死身游戏被转生苹果砸到（回关@天之神_†赛伊德† ⏰ 即日起 至 2026.6.8 💬 评论区交出你的启蒙游戏～ 往期互动

离谱的外号

本人姓冯，家里开厂（衣服厂） 由此获得了一个外号：缝纫机 还有 蚊子 冯牛马 等外号 那么大家身边有神马离谱的外号呢？ 欢迎留言

粉丝投稿/灌水/国内的游戏排名

没错这里是鸽了10天才发的粉丝投稿，国内的游戏排名！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本帖子为@💩💩百大游戏解说官💩💩提供灵感，感激不尽！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 观前提醒： 1. 粉丝给了我一个从未设想的道路（ ，但是因为我的游戏覆盖太少了，排名超级片面，如有误差请见谅（标粗的是我玩过的哦！） 2. 排行越靠后，资料越少，有些是他人收集的材料，真实性有待考量 3. 普及率并非一定是玩家，而是了解游戏就算 4. 算进排行内的一定是国服，国际不算在内（例如PUBGM）主服务器在国外也不算在内（例如minecraft） 5. 参与投稿必须先关注喵！然后私信我就可以啦！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 提要： 第一名：王者荣耀包含模拟器选手 第二名：和平精英包含刺激战场时期 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本次耗时：14小时 肝炸了求点赞QAQ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 关注@椰丝CO，不错过任何一个排名帖子！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 传送门炸了QAQ，进主页看吧 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 排名 游戏名称 年流水(预估) 累计玩家量 日活量 巅峰持续时间 普及率 综合评分 1 王者荣耀 ~350亿 超10亿 ~8000万 10年 95% 9.9 2 和平精英 ~170亿 超8亿 ~5000万 7年 92% 9.3 3 梦幻西游(端+手) ~200亿 超5亿 ~300万 21年 65% 8.9 4 DNF(端+手) ~150亿 超5亿 ~800万 16年 70% 8.7 5 原神 ~120亿 全球超6500万 ~500万 5年 85% 8.6 6 蛋仔派对 ~70亿 超6亿 ~3000万 3年 88% 8.4 7 三角洲行动(端+手) ~80亿 超1亿 ~2000万 2年 75% 8.3 8 金铲铲之战 ~60亿 超2亿 ~1500万 4年 82% 8.1 9 LOL(端游) ~50亿 超1.5亿 ~800万 14年 85% 8.0 10 崩坏：星穹铁道 ~60亿 超4500万 ~300万 2年 75% 7.9 11 CF(端+手) ~80亿 超6亿 ~500万 16年 86% 7.8 12 三国志·战略版 ~50亿 超3000万 ~150万 6年 60% 7.7 13 第五人格 ~40亿 超3亿 ~300万 7年 72% 7.6 14 火影忍者(手游) ~30亿 超1.5亿 ~200万 9年 68% 7.5 15 逆水寒(端+手) ~45亿 超5000万 ~200万 6年 65% 7.4 16 暗区突围 ~35亿 超1.2亿 ~300万 3年 62% 7.3 17 欢乐斗地主 ~25亿 超8亿 ~800万 17年 96% 7.2 18 开心消消乐 ~20亿 超8亿 ~600万 12年 95% 7.2 19 阴阳师 ~25亿 超3亿 ~100万 9年 65% 7.1 20 元梦之星 ~30亿 超1.5亿 ~500万 2年 70% 7.0 21 永劫无间(端+手) ~40亿 全球超4000万 ~200万 4年 65% 7.0 22 迷你世界 ~20亿 超6亿 ~500万 9年 76% 6.9 23 明日方舟 ~20亿 超2500万 ~80万 6年 55% 6.8 24 无畏契约 ~25亿 超3000万 ~200万 2年 60% 6.8 25 鸣潮 ~25亿 超2500万 ~100万 1年 50% 6.7 26 率土之滨 ~20亿 超2500万 ~80万 10年 50% 6.6 27 光·遇 ~15亿 超2亿 ~150万 5年 62% 6.5 28 QQ飞车(端+手) ~15亿 超3亿 ~100万 16年 66% 6.4 29 剑网3 ~15亿 超2亿 ~80万 16年 55% 6.3 30 捕鱼大作战 ~20亿 超4亿 ~300万 10年 72% 6.2 别忘了点赞！

谁是你的梦中情站！！！！！！！！！！！！

关注我一下，谢谢 --------------------------------------------------正文开始--------------------------------------------------------- 打个广告 打个广告2 1.游戏网站 poki(在小码王里用不了！！！555) Free Online Games on CrazyGames | Play Now!(这个可以用！！！happy这个老权威了) bloxd（和MC差不多，游戏多一点） florr（和zorr差不多） digdig(解压) zorr（和florr差不多） 4399(老游戏了) 360（还行吧） PCL 正版MC（非常牛B） 跑酷 跑酷2 空调(解压) 枪战 一些game 你画我猜 枪战游戏 海战 恐龙跳跳 领地 马里奥 2.学习网站 acgo本go 小码王本王 小白板 打字 洛谷 NOI GESP&&CCF 3.看视频的网站 抖音 哔哩哔哩 4.游戏下载 王者 taptap(在这里有很多游戏) 和平

深高北-贪心算法

贪心算法笔记（C++版） 一句话理解 > 贪心算法：每一步都选当前看起来最优的选择，不管以后会怎样。 就像吃自助餐——每次只拿最贵的菜，最后不一定吃得最爽，但在某些问题上这就是最优解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、什么是贪心算法？ 贪心算法：在每一步都做出当前状态下最好的选择，希望通过局部最优达到全局最优。 核心思想：只看眼前，不回头，不后悔。 特点： * 步骤简单，容易想 * 不一定每次都对（需要证明贪心是正确的） * 一旦正确，效率很高 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、贪心算法的基本框架 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、经典题目 题目1：活动安排（选最多的活动） 题目描述：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 e[i]。同一个时间只能参加一个活动，问最多能参加几个活动。 贪心策略：按结束时间从小到大排序，每次选结束最早的、且不冲突的活动。 输入样例： 输出样例： 为什么按结束时间选是对的？：结束越早，留给后面的时间越多。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目2：排队接水（平均等待时间最小） 题目描述：有 n 个人接水，第 i 个人接水需要 t[i] 分钟。问怎样排队能使所有人的平均等待时间最小？输出总等待时间。 贪心策略：按接水时间从小到大排队。 输入样例： 输出样例： （等待时间 = 0 + 3 + (3+1) + (3+1+4) + (3+1+4+2) = 0+3+4+8+5=20） 为什么按接水时间排序是对的？：用时短的人先接水，后面的人等得更少。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目3：找零钱（用最少硬币） 题目描述：有 1 元、5 元、10 元、20 元、50 元、100 元的硬币无限个。要支付 M 元，问最少需要多少硬币。 贪心策略：先用最大面额的硬币，不够再用小面额。 输入样例： 输出样例： （100+50+10+5+2+1？不对，这是金额。注意：M=168时：100元1个+50元1个+10元1个+5元1个+1元3个？等等算错了。100+50=150，差18，10元1个=160，差8，5元1个=165，差3，1元3个=168。一共1+1+1+1+3=7个。） 注意：这种贪心在人民币面额下是对的（因为每种面额都是更大面额的约数）。如果不是这种面额（比如1,3,4元，要付6元，贪心会选4+1+1=3个，但最优是3+3=2个），贪心不一定对。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、贪心的正确性 贪心算法不一定总是对的！使用前需要判断： 情况 说明 适用 问题有“贪心选择性质”（局部最优能推出全局最优） 不适用 当前选择会影响后面的选择 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、贪心 VS 其他算法 对比 贪心 动态规划 枚举 思路 每步选最优 考虑所有可能 全部试一遍 时间复杂度 通常 O(n log n) O(n²) 或更高 可能很高 正确性 需要证明 一定正确 一定正确 适用场景 有贪心性质的问题 最优化问题 数据范围小 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、贪心常见题型 题型 贪心策略 活动安排 按结束时间排序 排队问题 按时间排序 区间选点 按右端点排序 删数问题 找第一个下降点删除 找零钱 用最大面额（特定面额下） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、总结 要点 内容 核心思想 每步都选当前最好的 优点 简单、高效 缺点 不一定正确 使用前 证明或确认贪心是正确的 经典应用 活动安排 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 记忆口诀 > 贪心每步选最好，局部最优不烦恼 > 活动安排按结束，排队接水按时长 > 用前必须想清楚，贪心性质要记牢 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#创作计划 浅谈高级数据结构

吉司机线段树/历史最值 (ps：之前写过线段树总结，现在觉得这块内容放这个板块较为合适。) 很久以前用一知半解态度过的模板题，现在重新学习了下，不算难。 我的文章风格可能都有点刨根问底的感觉，理解的层次至少会阐述正确性（而不是说做法然后直接放代码）。 阅读门槛是需要知道线段树，标记合并。其实很低，如果势能分析看不懂也没关系。 PART1 区间最值操作 吉司机这个东西是可以在对数平方时间内维护区间最值修改的，操作如同： * 对 [l,r][l,r][l,r] 中的所有数执行 ai→min⁡(ai,k)a_i \to \min(a_i,k)ai →min(ai ,k)，其中 kkk 是给定常数。 当然上面的 min⁡\minmin 换成 max⁡\maxmax 也是完全可以的，我们先来阐明一下解决思路，再考虑时间复杂度的具体分析。 针对取 min⁡\minmin 操作进行讨论，另外的取 max⁡\maxmax 操作是完全对称的。在此基础上如果只需要查询最值则可以简单做到 O(nlog⁡n)O(n \log n)O(nlogn)，但这只是单纯的利用最值标记实现的简单线段树，并不是我们今天所讨论问题。所以，我们同时还需要支持查询区间总和等相关问题。 我们先明白查总和相对查最值更难做的原因，其实在于总和信息和取最值是没有结合律等优良性质的，刚刚所谈论的最值好做是因为操作和查询本身就支持信息合并。 更简单的说，单次修改中总和的修改量不能快速通过标记合并快速维护。所以我们必须考虑转化问题，这是线段树维护复杂信息的常见思路。本质在于让原问题变成更常见的问题，然后就可以很轻松地处理原问题。 一个简单的优化是跳过最大值小于等于 kkk 的节点，然而是不好直接做修改的。将问题转化为最小值大于等于 kkk 就做区间推平，特判叶子节点的想法。其实是完全不行的，因为最坏情况所有区间叶子都会被修改一次，修改总量完全没有保证，和暴力没有本质不同。所以我们需要做一个相对合理的批量修改方法。 换另一个可能更好的想法：维护最大值 maxnmaxnmaxn，最大值个数 cntcntcnt，严格次大值 sesese。修改的时候同样跳过最大值小于等于 kkk 的节点，并且当可以修改的节点满足 se<k≤maxnse < k \le maxnse<k≤maxn 就直接打删除标记 mul=k−maxnmul = k-maxnmul=k−maxn。这里表示将最大值区间加 mulmulmul，实际上效果相当于把最大值改成 kkk。维护一个标记 tagxtag_xtagx 表示当前节点 xxx 的最大值需要加多少就可以了，更新总和的时候贡献就是 tagx∗cnttag_x * cnttagx ∗cnt。 这里其实我们可以发现一件事情：最大值被单独列出维护了一个标记。这意味着如果还需要支持其他操作：比如区间加。则我们必须要维护两套标记：一个是针对最大值的，一个是针对除最大值以外的所有数。 其实底层原因也很简单，就是因为最大值对于的区间加标记不会作用于其它数上，就导致最大值所需要考虑的信息更多，当然如果这些信息不会影响到某种标记合并也可以分开维护。 首先考虑两个问题：答案正确性和时间复杂度分析。答案的正确性是比较显然的，接下来考虑时间复杂度的分析。这里其实直接分析单次修改是很容易绕弯子的，事实上证明用了一个高级技巧：势能分析。 在这里我会尽量用文字阐述下证明思路和过程，这里我们引入一个概念函数 W(u)W(u)W(u)，其满足以下性质： * 当节点 uuu 的最大值不等于其父亲节点的最大值时，有 W(u)=1W(u) = 1W(u)=1。 * 否则都有 W(u)=0W(u) = 0W(u)=0。 因为我们访问节点 uuu 需要的代价实际上是还需要考虑深度，换句话说总势能在 O(nlog⁡n)O(n \log n)O(nlogn) 量级，也就是 ∑W(x)×depx\sum W(x) \times dep_x∑W(x)×depx ，这里一个节点的深度可以粗略的看做 log⁡n\log nlogn。 然后我们考虑分析修改操作对势能总和的相对影响，这个所谓的势能实际上可以简单认为它等于程序总运行次数（也就是时间复杂度总量）。 至于根本原因，完全可以这样理解： * 考虑一个节点 xxx 满足 W(x)=0W(x) = 0W(x)=0，我们发现此时必然满足 maxnx<maxnfxmaxn_x<maxn_{f_x}maxnx <maxnfx ，此时 maxnxmaxn_xmaxnx 只能贡献到 sefxse_{f_x}sefx 。又因为此时暴力递归必有 sefx<kse_{f_x} < ksefx <k，所以我们知道 xxx 这个节点不可能会被暴力递归访问到，访问它的时间复杂度是 O(log⁡n)O(\log n)O(logn) 级别的，所以我们就依据这个性质设计势能函数值为 W(x)×depxW(x) \times dep_xW(x)×depx 。 同时，只需要聚焦于因为值域问题暴力递归处理节点的情况。其他情况就是普通线段树的时间复杂度。 回到势能分析中，当节点 xxx 的次大值 sesese 大于等于 kkk 时，我们显然有： * 两个子节点 lsxls_xlsx 和 rsxrs_xrsx 的最大值一定大于等于 kkk。 * 其中一定有一个孩子（不妨设为 rsxrs_xrsx ）的最大值小于 xxx 的最大值，否则如果两个子节点最大值都等于 maxnxmaxn_xmaxnx ，则次大值不可能 ≥k\ge k≥k。除非子树内有更深的分裂，这会在继续递归的儿子中被讨论，这里直接认为就是满足条件的。 当我们在该子树执行完操作并向上回溯后： * lsxls_xlsx 和 rsxrs_xrsx 的最大值由于被 kkk 截断，现在全部变成了 kkk。 * 父亲节点 xxx 的最大值也更新为 kkk。 * 此时，由于 maxnrsx=maxnx=kmaxn_{rs_x} = maxn_{x} = kmaxnrsx =maxnx =k，原本不相等的最大值现在对齐了。于是，W(rsx)W(rs_x)W(rsx ) 从 111 变成了 000。 势能减少了，严格来说减小的势能实际上是 deprsx=depx+1dep_{rs_x} = dep_x+1deprsx =depx +1。 由于 xxx 是暴力递归节点，虽然我们在当前层花费了 O(1)O(1)O(1) 的常数时间，但我们成功让一个深度为 depx+1dep_x+1depx +1 的节点的 WWW 归零，释放了 depx+1dep_x+1depx +1 的势能。同时也可以通过这个方面说明每一次暴力递归都可以在后续递归中找到某个节点，让它势能 WWW 归零来为时间复杂度的开销买单。 同时还需要分析区间加操作带来的势能变化，一共会拆成 log⁡\loglog 个节点，最坏情况下每个节点 xxx 的父亲 fxf_xfx 的另一个儿子的势能由 000 变成 111，总变化量量级至多为 O(qlog⁡2n)O(q \log ^2 n)O(qlog2n)。并且加标记下传不会影响势能 WWW 变化，增减势能的情况就上面两种。 势能总量为 O((n+q)log⁡2n)O((n+q) \log^2 n)O((n+q)log2n) 量级，单次操作会增加或消耗 O(log⁡2n)O(\log ^2 n)O(log2n) 的势能，总时间复杂度自然为 O((n+q)log⁡2n)O((n+q) \log ^2 n)O((n+q)log2n)。 当时吉老师的论文如果我没记错的话是修改的势能分析错判为 O(log⁡n)O(\log n)O(logn)，并且其实势能增量卡慢其实不简单，所以实际表现和常数大一点的 O(nlog⁡n)O(n \log n)O(nlogn) 没什么区别。 PART2 历史最值 这块部分严格来说和最值修改完全没关系，一个位置的历史最值的定义是该位置上的数在所有时刻中的最值。相对吉司机要简单很多。 同样的，我们考虑历史最大值的做法，记 AiA_iAi 表示当前时刻位置 iii 上的值，BiB_iBi 表示所有时刻位置 iii 的最大值。实际上我们是在维护的历史最大值可以看做一个前缀时间内数的最大值。 首先我们要维护的区间历史最值显然只会被区间最大值更新，换到线段树上就是考虑标记的合并与迭代。只维护加标记 tag1tag_1tag1 的想法是错误的，原因在于标记可能经过多次合并，实际意义就是加了很多次数。我们一定会考虑维护 tag1tag1tag1 的历史最大值，记作 tag2tag2tag2,用它来更新答案。 由于标记下传后贡献已经清除，所以本质上我们只是在维护： * tag1tag1tag1 表示上一次下传标记后到现在的加标记。 * tag2tag2tag2 表示上一次下传标记后到现在的时刻中，tag1tag_1tag1 的最大值。 同时记最大值为 m1m_1m1 ，历史最大值为 m2m_2m2 。考虑下传节点 xxx 的标记： * tag1sonx→tag1sonx+tag1xtag1_{son_x} \to tag1_{son_x} + tag1_xtag1sonx →tag1sonx +tag1x ，加标记合并。 * tag2sonx→max⁡(tag2sonx,tag2x+tag1sonx)tag2_{son_x} \to \max(tag2_{son_x},tag2_x+tag1_{son_x})tag2sonx →max(tag2sonx ,tag2x +tag1sonx )，理由很简单，此时 xxx 标记对 sonxson_xsonx 的影响在于 tag1xtag1_xtag1x ，而由于我们维护的 tag1xtag1_xtag1x 实际上是一个时间点的加标记，换句话说是落在该节点的加操作之和。本质上我们应该遇到一个操作就直接下传儿子修改，但是为了复杂度我们选择了延迟下传，所以就会选择使用 tag2xtag2_xtag2x 更新。正确性只需要考虑 tag2xtag2_xtag2x 合法（一定是某个时刻的 tag1xtag1_xtag1x ）并且最优（根据定义它最大）。 然后依据历史最大值标记的最大贡献 tag2x+m1(x)tag2_x+m1(x)tag2x +m1(x) 取更新 sonxson_xsonx 的 m2m_2m2 即可。整个过程的设计思路比较自然。 PART 3 结合问题 模版题把两个问题合并在了一起，实际上做法还是依据上述思路维护线段树信息，之前在第一部分我也顺便提到过：由于吉司机把最大值单独考虑，所以要针对最大值和非最大值设计两种标记组。 什么意思，就是实际上我们需要维护四个标记 tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4tag1,tag2,tag3,tag4，但是其实是因为 tag1,tag2tag1,tag2tag1,tag2 服务于区间最大值（定义同第二部分），其余的 tag3,tag4tag3,tag4tag3,tag4 服务于其余所有数，本质上只是迫不得已维护了两套一模一样的标记而已。 这段代码是在处理节点 xxx 加入的四个标记分别为 v1,v2,v3,v4v1,v2,v3,v4v1,v2,v3,v4 后的影响。首先更新和，考虑最大值个数和其余数个数（里面 clenxclen_xclenx 是节点 xxx 代表的线段树区间长度）和标记组合即可。剩下的都是刚刚推导里面就有的，注意这里需要判断次大值是否存在的情况。 然后考虑标记下传函数： 这段代码考虑了 W(sonx)W(son_x)W(sonx ) 的情况，也就是说我们需要考虑某个儿子的最大值是不是节点 xxx 的最大值，如果不是则不需要考虑最大值标记信息不同带来的影响。因为下传的 tagtagtag 是以节点 xxx 的视角设计的，下传到 sonxson_xsonx 需要变换成 sonxson_xsonx 的视角，也就是说如果 sonxson_xsonx 本身对最大值没贡献则会被自动规约到 tag3x,tag4xtag3_x,tag4_xtag3x ,tag4x 的管辖范围。 关键代码如下： 当然如果操作需要支持取最大值或者最小值，维护思路完全一样。但是值得注意的一点是注意特判重复贡献。理论上维护三套标记的话其中两套分别是为最大值和最小值服务的，但是如果一个数同时是最大值和最小值需要特别判断。除此之外，也需要考虑最大值同时是次小值，最小值同时是次大值的情况（不然非最值标记会重复贡献）。 总而言之这是一个相对高级的线段树技巧，但是理解起来也不是特别困难。

官方题解 | 挑战赛#32题解

赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。 题目编号 题目名称 题目难度 T1 项目计划 入门 T2 千载难逢的良缘 普及- T3 保险金 普及- T4 晋级赛 普及- T5 科技展示 普及- T6 活动筹备计划 普及- T1 项目计划 题目大意 给出项目数量和产线数量，并给出完成项目所需的时间，所有项目的时间都是给出的这个时间。求完成所有项目所需的总时间。 题解思路 先用取余运算确定完成所有项目所需的轮数，如果无法整除则需要单独再增加一轮时间。确定轮次之后计算总时间，可以先单独计算时分秒，再按秒分时的顺序进行进位判断。 需要注意输入的格式中存在 : 分隔符，需要用提示中的 scanf 获取，或在读取时注意 : 的位置。 参考代码 T2 千载难逢的良缘 题目大意 给出每个人的平分，评分差值的绝对值越小越有缘，求最有缘的两个分数以及他们的差值绝对值。 题解思路 差值绝对值最小的两个分数一定是大小最接近的，所以整体排序后遍历整个数组，记录其中差值绝对值最小的情况。 参考代码 T3 保险金 题目大意 给出每个客户的 mmm 条事故保险金，要求按照客户顺序处理，每个客户内按金额从小到大处理，直到当天能发放的保险金总额不够继续发放。 题解思路 按题目要求的顺序排序，可以使用结构体排序，按客户编号和金额大小排序，再模拟发放过程即可。 需要注意题目要求的输出格式，当遇到新客户时要输出名字和发放事故数，再输出每个事故的保险金数量。所以这里要记录上一个发放事故的客户编号，区分不同的客户。在输出时也要先遍历统计数量，再遍历输出对应的面额。 参考代码 T4 晋级赛 题目大意 给出选手分数，查询多个分数对应的无法晋级人数。 题解思路 由于是多次查询，因此可以先排序，再使用二分查找的方法查询晋级分数所在的数组下标，从而得到无法晋级的下标范围。 参考代码 T5 科技展示 题目大意 给出 n 件展品，选择 m 件展品，要求方案输出时编号按升序排列。 题解思路 经典深度优先搜索抽小球，需要注意用 vis 数组记录哪些展品已经选择。但本题中要求编号按升序排列，因此在递归时可以加入编号范围的参数，用于控制选取时的循环范围，确保选取编号是升序。 参考代码 T6 活动筹备计划 题目大意 三种任务在每天有不同的效果值，不能连续两天选择相同的任务，切换任务会获得对应的切换效果值。求 nnn 填的最大总效果值。 题解思路 由于每天每个任务的效果值都可能变化，所以选择动态规划，状态转移方程形如 dp[i][0]=max(dp[i-1][1]+w[1][0],dp[i-1][2]+w[2][0])+val[i][0];，其中 w[i][j] 表示切换任务 i 到任务 j 的效果值，val[i][j] 表示第 i 天完成任务 j 的效果值。 类似于涂色问题，由于选择任务时不能和前一天的任务相同，因此需要记录前一天选择的任务编号，重复的情况是无法转移的，同时前一天的任务编号也参与了切换效果值的计算。在 dp 数组的设计中选择二维形式，dp[i][j] 表示第 i 天选择任务 j 的最大总效果值。 参考代码