AC罐头商店 使用说明 💰 一、罐头获取方式 刷题赚罐头 🎯 获取方式 罐头奖励 说明 攻克新题 1-7罐头/题 每成功攻克一道自己未AC的官方题目，根据题目难度获得罐头：• 入门：1罐头；• 普及-：2罐头；普及/提高-：3罐头；• 普及+/提高：4罐头；• 提高+/省选：5罐头；• NOI/CTSC级别：7罐头；每日上限：5题（即每日最多通过5道新题获得罐头） 题目首杀 5-35罐头/题 首位攻破“零通过”的官方题目，根据题目难度获得• 入门：5罐头；• 普及-：10罐头；• 普及/提高-：15罐头• 普及+/提高：20罐；• 提高+/省选：25罐头；• NOI/CTSC级别：35罐头 ；每日上限：5题（即每日最多通过5道首杀获得罐头） 首次竞赛报名 20罐头 用户第一次报名ACGO的官方竞赛时获得 排位等级晋升 100-800罐头/级 排位等级从上一级晋升到下一级时获得（每个等级仅奖励一次）：• 青铜→白银：100罐头；• 白银→黄金：200罐头；• 黄金→铂金：300罐头；• 铂金→钻石：400罐头；• 钻石→大师：600罐头；• 大师→王者：800罐头 天梯闯关过关 1-200罐头/关 每通过一关天梯闯关即可获得罐头，奖励金额随关卡难度递增，具体以关卡实际显示为准 活跃赚罐头 🎪 获取方式 罐头奖励 每日上限 每日点赞 1罐头/次 5次（5罐头） 每日评论 1罐头/次 5次（5罐头） 每日收藏题单 1罐头/次 5次（5罐头） 帖子被点赞 1罐头/次 10次（10罐头） 题单被收藏 5罐头/次 10次（50罐头） 每日活跃罐头上限：75罐头（5+5+5+10+50） 运营与贡献 🏆 获取方式 罐头奖励 说明 管理员手动发放 50-5000罐头 适用于以下场景：• 参与各类赛事并按赛事规则分配奖励；• 贡献优质题解、技术分享等内容被官方采纳；• 为社区发展提供特殊贡献等 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⏰ 二、罐头过期说明 滚动过期规则 AC罐头采用 【滚动过期】 方式管理： 1. 过期时间：每个自然年年底（12月31日23:59） 2. 过期范围：上一个年度获得且未消耗的罐头 3. 过期示例： * 2024年获得的罐头，将在2025年12月31日23:59过期 * 2025年获得的罐头，将在2026年12月31日23:59过期 * 以此类推... 过期提醒服务 * 提醒时间：每年12月1日开始 * 提醒方式： * 站内信通知 * 平台置顶帖子公告 * 提醒内容：“您有XXX罐头即将在12月31日到期，请尽快兑换！” 过期应对策略 1. 及时消费：不要过度囤积罐头，看到心仪商品及时兑换 2. 年度规划：每年11月开始规划罐头使用，避免年底过期浪费 3. 关注提醒：每年12月注意查看站内信和公告 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💡 三、重要提醒 1. 罐头与账号绑定，不可转让、不可交易 2. 商品一经使用，概不退换，请确认后再购买 3. 请合理安排罐头使用计划，避免过期造成浪费 每年年底记得清空旧罐头，迎接新一年的赚罐头之旅！ 🎉

挑战赛27题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的矩形 入门 T2 午枫的字符串移动2 入门 T3 午枫打砖块 普及/提高- T4 午枫的子序列之和 普及/提高- T5 午枫的星星树 普及- T6 午枫的数字华容道 普及/提高- T1 午枫的矩形 题目大意 给定一个矩阵，判断这个矩阵的任意子矩阵是否满足 左上角的数+右下角的数≤左下角的数+右上角的数左上角的数+右下角的数\leq 左下角的数+右上角的数左上角的数+右下角的数≤左下角的数+右上角的数 。 解题思路 由于数据范围只有 1≤n,m≤501\leq n,m\leq 501≤n,m≤50 ，所有直接四层循环嵌套枚举左上角和右下角，同时也能知道左下角和右上角的坐标，直接计算判断即可。 参考代码 T2 午枫的字符串移动2 题目大意 给定一个字符串，可以进行左移和右移的操作任意次，找到所有可以得到的字符串中字典序最小以及最大的字符串。 解题思路 因为可以操作任意次，所以只要单独往一个方向不断移动并且更新字典序最小和最大的字符串即可。 这里可以直接使用 string 类型进行移动的操作，并且也可以使用 min 和 max 函数进行比较字典序大小。 参考答案 T3 午枫打砖块 题目大意 给定 nnn 行砖块，每行向右无限延伸并且有且有一段连续的区间为奖励砖，每次可以选择一个区间长度 ddd ，并且将这 ddd 列每行所有的砖块都破坏，奖励砖只要被破坏一个格子就会被全部破坏，求将所有奖励砖都破坏需要的最少操作次数。 解题思路 这是一道经典的贪心问题，在排序时我们会想到，如果破坏一个奖励砖的最右端，那么就会破坏更多的奖励砖，所以我们按照右端点排序，模拟每次打破当前剩余第一个奖励砖的最右端即可。 参考答案 T4 午枫的子序列之和 题目大意 给定一个长度为 nnn 的数组和一个整数 kkk ，求数组 aaa 的所有连续子序列中，元素之和等于 kkk 的个数。 解题思路 首先我们可以预处理前缀和数组 sss ，即需要求区间满足 sr−sl−1=ks_r-s_{l-1}=ksr −sl−1 =k 的区间个数。问题就转化成了非常经典的问题。 枚举区间右端点 rrr ，同时统计已枚举前缀每个 sls_lsl 的个数，那么对于这个 rrr ，对答案贡献为满足 sl−1=sr−ks_{l-1} = s_r - ksl−1 =sr −k 的所有 lll 的个数。那么问题又进一步简化为：统计 si=xs_i = xsi =x 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。 参考代码 方法一：map 方法二：离散化 T5 午枫的星星树 题目大意 给定一棵树，问是否存在一个点与其他所有点直接相连。 解题思路 记录所有点的度数，判断是否存在一个点的度数为 n−1n-1n−1 即可。 参考代码 T6 午枫的数字华容道 题目大意 有 999 个点 mmm 条边的无向图，其中有 888 个数字放置在不同点上，有一个没有数字的点，可以通过移动将数字移动到相邻没有数字的点上，求最终将数字 1∼81\sim 81∼8 分别放在顶点 1∼81\sim 81∼8 上的最少操作次数。 解题思路 我们可以将 999 个顶点上所存放的数字用字符串表示状态，例如 254806137 表示顶点 111 存放数字 222 ，顶点 222 存放数字 555 ，依此类推，特殊地，数字 000 表示该点为空。那么终点就可以用 123456780 表示。 由于每次移动都会从一种状态变为另一种状态，我们不妨将每种状态看作一个结点，那么所有状态以及状态与状态之间的变换就可以形成一张无向图，于是我们只需要在图上用 bfsbfsbfs 跑最短路即可。由于结点是以字符串表示的，所以可以使用 map 存储从起点状态到达所有状态结点的最短路径长度。 参考代码

终于补完离线算法了（ 莫队是三大离线算法之一（毒瘤且少用的线段树分治不算），同时也是许多人入坑的第一种离线算法。虽然思路比较简单，但是莫队题型多、容易出错、写代码时常常粗心，部分理论可能难以理解，本创作计划旨在帮助读者完善莫队知识盲点、学习带修和回滚莫队的思想（因为网上的资源比较难懂，本人也曾深受其害）。 关于莫队，有个特点是代码比较好写，常数也很小。难绷三大离线算法两个（莫队和整体二分）常数小得逆天容易跑得比同复杂度甚至更优复杂度解法快还特别适合 O2 一个（CDQ 分治）就常数大（使用大量 sort 的话还会明显变慢）然后天天被 K-D 树和多维分块（WorldMachine%%%)打压。 莫队是什么 > 莫队算法是由莫涛提出的算法．在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人．莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本. > 莫队算法可以解决一类离线区间询问问题，适用性极为广泛．同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作．(from OI-wiki) 从一道模板题入手。 P2709 【模板】莫队 / 小B的询问 题目描述 小 B 有一个长为 nnn 的整数序列 aaa，值域为 [1,k][1,k][1,k]。 他一共有 mmm 个询问，每个询问给定一个区间 [l,r][l,r][l,r]，求： ∑i=1kci2\sum\limits_{i=1}^k c_i^2 i=1∑k ci2 其中 cic_ici 表示数字 iii 在 [l,r][l,r][l,r] 中的出现次数。 小 B 请你帮助他回答询问。 输入格式 第一行三个整数 n,m,kn,m,kn,m,k。 第二行 nnn 个整数，表示小 B 的序列。 接下来的 mmm 行，每行两个整数 l,rl,rl,r。 输出格式 输出 mmm 行，每行一个整数，对应一个询问的答案。 说明/提示 【数据范围】 对于 100%100\%100% 的数据，1≤n,m,k≤5×1041\le n,m,k \le 5\times 10^41≤n,m,k≤5×104。 总之就是询问你一个区间里每个数出现次数的平方加起来是多少。 这题维护的东西用普通 ds 和算法维护看上去很不可做。如果用暴力呢？ 我们只需要定义一个 cnt 数组，定义 cnticnt_icnti 表示数值 i 在序列中出现的次数。当加入一个新数时，把当前答案加上这个原来出现的次数再 +1 就行了。很容易证明正确性。但是这样复杂度是 O(NM)O(NM)O(NM). 而莫队算法仅用了一个排序的技巧，就优化了时间复杂度。如何做到？ 首先，假设我们有大量询问： （画得丑致歉） 注意到不同区间有很多重复的地方，在询问中会被重复计算，这个地方能不能节省呢？ 先看看以下情况： 只需要将粉色区间左端点略微右移，右端点也右移就与绿色区间一样了。 莫队为了节省这些计算，将数列分为 N\sqrt NN 块（假设 N=M)，每一块长度为 N\sqrt NN .接下来对询问进行排序，将询问按左端点所在的块从左到右排序，左端点所在块一样则按右端点升序排序。然后按照排序顺序从前到后处理询问，存储上一次询问的左端点和右端点，并对其进行移动使得左端点和右端点与当前询问吻合，然后存储当前答案。 对于本题，左端点和右端点的移动都是 O(1)O(1)O(1) 的。 时间复杂度是多少？ 每次处理新的询问，左端点和右端点都会进行移动。对于左端点的移动，由于对左端点所在块排序，所以一个块内询问左端点的移动一次是 O(N)O(\sqrt N)O(N ). 如果要到右边的块，由于一个块长度为 N\sqrt NN , 也只需要 O(N)O(\sqrt N)O(N ) 的时间复杂度进行一次移动。总共进行 M 次移动，因此所有左端点移动的时间复杂度是 O(MN)O(M\sqrt N)O(MN ). 那么右端点的移动呢？对于每个块内的询问，右端点是从小到大递增的，所以一个块内右端点的移动共为 N 次，总共有 N\sqrt NN 个块，所以移动右端点的时间复杂度为 O(NN)O(N\sqrt N)O(NN ). 两者相加，O(MN)+O(NN)=O(NN)O(M\sqrt N)+O(N\sqrt N)=O(N\sqrt N)O(MN )+O(NN )=O(NN )（N=M) 本题要怎么移动左端点和右端点？当左端点向左时，新添加的数 x 给答案做的贡献是 (cntx+1)2−cntx2=2×cntx+1(cnt_x+1)^2-cnt_x^2=2\times cnt_x+1(cntx +1)2−cntx2 =2×cntx +1, 因此我们先将答案加上 2×cntx+12\times cnt_x+12×cntx +1, 再更新 cnt 数组即可。其它移动操作自己推。 本题数据为 1≤n,m,k≤5×1041\le n,m,k \le 5\times 10^41≤n,m,k≤5×104, 时间复杂度正确。 小优化：大部分莫队可以用奇偶性优化减少常数。对于左端点为第奇数块的询问，右端点从左到右排，否则从右到左排。如图所示： 注：实际上是曼哈顿距离，这里为了方便画的是欧式距离。 这个优化最多优化一半的计算量，一般可以提升几十毫秒的速度，但是也有一些数据反而会跑更久。 还有一点需要注意：初始 l=1,r=0. 记住，当莫队需要在 x 和 x+1 直接设置初始位置并向左右分别扩展时，l=x+1,r=x. 以下是本题代码： 这段代码采用的是莫队常用的写法，其中 &1 可以判断一个数是否为奇数。 请对照模板题代码自己理解。 莫队分块 当 N=M 时，分块大小为 N\sqrt NN 最优。但是当 N≠MN\neq MN=M 时，分块为 NM\frac{N}{\sqrt M}M N 是最优的。这时候左端点移动复杂度为 O(M×NM)=O(NM)O(M\times \frac{N}{\sqrt M})=O(N\sqrt M)O(M×M N )=O(NM ), 右端点移动复杂度为 O(M×N)=O(NM)O(\sqrt M\times N)=O(N\sqrt M)O(M ×N)=O(NM ), 总时间复杂度为 O(NM)O(N\sqrt M)O(NM ) 普通莫队例题 P1494 [国家集训队] 小 Z 的袜子 自行看题。 如何回答询问？我们需要知道区间内每一种颜色的袜子抽到一样的方案数，除以区间总方案数。区间总方案数的计算是入门的。很明显我们要维护 cntx×(cntx−1)2\frac{cnt_x\times (cnt_x-1)}{2}2cntx ×(cntx −1) . 最后那个 12\frac{1}{2}21 不用维护，因为会约分所以只要总方案数也不乘以 12\frac{1}{2}21 就能抵消了。像上题一样维护 cntx2cnt_x^2cntx2 就行了，维护完还要对每个 xxx 减去 cntxcnt_xcntx （由上式可知）, 由于一个区间里所有出现数值 xxx 的出现次数之和就是这个区间的长度，因此求出 ∑cntx\sum{}^{}cnt_x∑cntx 后直接减去区间大小即可。每个查询算完还要进行约分，但是约分时间复杂度较小直接并入总复杂度。以下代码进行了特判，但是似乎这个方法实现不需要特判。 Code:Code:Code: P1997 FAEBDC 的烦恼 本题其实就是让你求区间众数出现的次数。 普通莫队似乎不能维护删除操作，因为区间众数是回滚莫队才能维护的。但是，不要小看普通莫队啊！ 设 maxn 为答案，每个询问不重置 maxn, 仅改动 maxn. 加入操作可以通过 c(cnt) 数组直接维护最大值。那么删除操作如何实现？设 ccicc_icci 为 i 在 c 中出现的次数，删除第 i 个数字时如果 ccci＞1cc_{c_i}＞1ccci ＞1 则直接将 cccicc_{c_i}ccci 减一， cic_ici 更新后再将当前 cccicc_{c_i}ccci 加一。当删除元素等于众数且众数只有一个时，依旧维护以上两个数组并将 maxn 减一，因为原来的众数都没了，刚刚删掉一个原来出现了 maxn 次的众数，所以现在这个数出现的次数为 maxn-1. Code:Code:Code: P11659 小夫 注意到出题人又让我们维护不是人的东西了，所以容易联想到莫队。怎么维护呢？ 维护三个数组：cnt,cnt42,cnt23. cnticnt_icnti 表示 i 在区间内出现的次数，cnt42icnt42_icnt42i 表示序列中 l≤x<y≤r,ax=4×i,ay=2×il\le x<y\le r,a_x=4\times i,a_y=2\times il≤x<y≤r,ax =4×i,ay =2×i 的二元组数量， cnt23icnt23_icnt23i 表示序列中 l≤x<y≤r,ax=2×i,ay=3×il\le x<y\le r,a_x=2\times i,a_y=3\times il≤x<y≤r,ax =2×i,ay =3×i 的二元组数量。 左端点左移时，加入一个数，先不更新 cnt(因为要用到原来序列的 cnt) ,如果 ala_lal 可以被 4 整除，cnt42al4cnt42_{\frac{a_l}{4}}cnt424al 要加上与 ala_lal 符合 4:2 比的数的个数，即 cntal2cnt_{\frac{a_l}{2}}cnt2al , 同时也更新答案，将答案加上 cnt23al4cnt23_{\frac{a_l}{4}}cnt234al . 如果 ala_lal 可以被 2 整除，cnt23al2cnt23_{\frac{a_l}{2}}cnt232al 要加上 cntal×32cnt_{a_l\times \frac{3}{2}}cntal ×23 . 其它操作也按这个原理做，注意删除操作要先更新 cnt. 注：数组要开两倍，自己想为什么。 Code:Code:Code: 经过以上锻炼，可以发现莫队的优势是可以维护其它东西很难维护的条件，但是相对应的，莫队是一个离线、不便于修改的算法，具有一定的局限性。 带修莫队 带修莫队有什么用基本没题考 以上的莫队都是只查询不修改的。那要是加上单点修改呢？ 对于 CDQ 分治有大量经验的你可能会想到，把时间也看成一个维度进行排序不就行了？将询问进行排序，然后左端点、右端点、时间一起移动成当前询问。时间移动时如果往后移动就按顺序修改，往前就倒序回溯过去。 带修莫队的操作是将元素按左端点所在块排序，一样则按右端点所在块排序，还是一样就按时间从小到大排（一个询问的时间为这个询问前面进行的修改操作的数量）。 但是分块显然要改了，因为如果还是按原来分的话时间维度的总移动复杂度是 O(NM)O(NM)O(NM) ，显然这不是我们想要的。这个时候你会干什么呢？ 当块长为 N23N^{\frac{2}{3}}N32 时，左端点移动的时间复杂度是 O(N23×M)=O(MN23)O(N^{\frac{2}{3}}\times M)=O(MN^\frac{2}{3})O(N32 ×M)=O(MN32 ), 右端点移动一样是 O(MN23)O(MN^\frac{2}{3})O(MN32 ), 时间移动是 O(N13×N13×M)=O(MN23)O(N^{\frac{1}{3}}\times N^{\frac{1}{3}}\times M)=O(MN^\frac{2}{3})O(N31 ×N31 ×M)=O(MN32 ), 所以总的时间复杂度还是 O(MN23)O(MN^\frac{2}{3})O(MN32 ). 例题：P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列 直接上代码。注意本题的单点修改直接将 aci,pa_{c_{i,p}}aci,p 与 ci,colc_{i,col}ci,col 交换（把要修改的原位置值和修改操作的新值调换），这和人不能连续向一个方向跨过同一条河流是一个道理，当你执行了一次修改操作后当前时间就会大于这个操作的所在时间，所以下一次调用这个函数只有一种可能：当前时间在减小，即时间回溯操作，这时候再调换回来即可。 Code:Code:Code: 带修莫队似乎没什么用同时这题还有 O(Nlog2N)O(Nlog^2N)O(Nlog2N) 的树套树和 CDQ 分治解法，学习了 CDQ 分治的读者可以尝试，因为这题其实就是P4690 [Ynoi Easy Round 2016] 镜中的昆虫的弱化版。虽然是 Ynoi easy round 的…… （偷图致歉） 回滚莫队 他们说回滚莫队没用，我觉得有用。 回滚莫队有两种：不删除莫队（有点用）和不添加莫队（有存在必要吗）。不添加莫队我没见过题，更不会做，也不会写，所以不讲，知道怎么计算初始整体状态并且能翻到例题的请容我%%%。 不删除莫队用于莫队算法添加容易删除难的情况。以下是例题： P14420 [JOISC 2014] 历史的研究 / Historical Research 题目要你求序列内一个数的值乘以这个数出现次数的积的最大值。添加元素只需要将出现次数更新然后取答案最大值就行了。如何删除？ 不删除！ 接下来我们使用显性分块编码，存储每个位置所在块和每个块的左右端点。 先假设我们的所有询问左右端点都在不同的块上，即右端点所在块在左端点所在块右边。 回滚莫队遍历每一个块，一开始将 l 设为这个块右端点位置+1，r 设在右端点。 然后先扩展右端点。 我们将这个答案保存，然后扩展左端点。 这时候记录答案。这时候，我们将 l 一步步右移，把辅助数组回溯成原来的样子。注意，是回溯不是删除（因为答案没有更改）。 到了下一个询问，初始答案直接设为上次保存的答案就行了，然后在区间基础上扩展右端点，因为右端点是递增的只需要添加，情况又回到了一开始。以此类推，这个块算完了就跳到下一个块。整个过程只用了添加和回溯操作，答案不通过回溯更新（因为答案更新更难）而是直接用上次答案。注意到回溯操作根本不用复杂维护，只要你能确保辅助数组回到上次状态就行。 时间复杂度是多少？左端点的移动一次 O(N)O(\sqrt N)O(N ), 右端点也没变，所以还是 O(NN)O(N\sqrt N)O(NN ) 的时间复杂度。 等等，那左右端点在同一块的询问呢？直接暴力就行了，因为这时候一次暴力 O(N)O(\sqrt N)O(N ). 很容易想到，回滚莫队自然不能用奇偶性优化了。 对于这道例题，我们依旧 cnt 数组，扩展时先更新 cnt 再更新最大值，回溯 cnt 时遇到一个就将它的 cnt 减去 1. 暴力是有手就行的。其实这题就是一道变形的区间众数。 注意看 Code:Code:Code: 闲话：这个模板也是我选的而不是洛谷官方模板，回滚莫队和线段树合并一样都是有一道题既用到知识点又最简单然后被推崇为模板但是官方模板却要经过一定的思考。不过雨天的尾巴这个名字好好听啊你值得模板之名QvQ. 既然已经做出了这道题那么区间众数也很简单了： P13984 数列分块入门 9 回滚莫队入门9（误） 所以 Ynoi 是不是叫数列分块提高 更新答案时就不用乘以这个数的值了。注意到要求出现次数一样时答案为最小者，所以要保存两个答案：答案出现次数和答案数值大小，方便比较更新。 同时此题告诉我一个很重要的点：调回滚莫队一定要把每次遍历块时初始化的那个（些）变量当作实际维护的答案，不要当成中间值变量。小朋友们不要忘记一开始初始化辅助数组哦。 此题套模板做的 6 分钟一道紫我太强了 Code:Code:Code: 此题的效率也跑到了一个丧心病狂的程度： 接下来是真正的模板题： P5906 【模板】回滚莫队&不删除莫队 本题独立 3 分钟解出来我太强了我要进省队了 这题可以维护 4 个数组，左端点左移遇到的某数的最左值、左端点右移遇到的某数的最右值、右端点左移遇到的某数的最左值、右端点右移遇到的某数的最右值，最左/最右取左右端点答案的最值即可得到，记得要初始化数组，回溯时将左端点遇到的最左和最右端的值都回溯成初始化时的状态即可。当然我还开了两个数组进行暴力。不会你们学回滚莫队尝试自己默时忘记写暴力了吧。 Code:Code:Code: 回滚莫队的例题有点少，但是当比赛遇到普通莫队题然后删除操作怎么都想不出来时应该可以试试回滚偷 AC. 莫队＋根号分治/值域分块 莫队算法需要进行 (N+M)N(N+M)\sqrt N(N+M)N 次增删操作和 MMM 次答案记录操作，这就导致莫队特别适合出一些考察复杂度平衡的题。 P12598 参数要吉祥 别争论扶苏是男的还是女的了，扶苏是一个大语言模型。 由于是非人哉的东西所以可以想到莫队。莫队怎么维护呢？ 首先删除和添加可以很容易地维护出现次数 c 和出现次数出现的次数 cc,但是怎么快速地把每个值不为 0 的 ci×cccic_i\times cc_{c_i}ci ×ccci 抓出来呢？ 暴力显然不现实。所以…… 设分块的大小为 t, 我们先遍历整个数组，把值小于 t(就是 N\sqrt NN ) 的 cic_ici 的值存在一起（这种值最多有 N\sqrt NN 个），另外存储存储满足 ci>tc_i>tci >t 的 i. 因为 c 代表的是一个数出现的次数，而出现次数大于 N\sqrt NN 的数最多只能有 N\sqrt NN 个，所以这部分数的数量最多也是 N\sqrt NN . 随后进入莫队环节，每次移动完区间后遍历这两个表更新答案，每个询问需要 O(N)O(\sqrt N)O(N ) 的时间复杂度，总共 O(MN)O(M\sqrt N)O(MN ), 总体复杂度依然是 O((M+N)N)O((M+N)\sqrt N)O((M+N)N ). Code:Code:Code: P4867 GTY的妹子序列 自行读题。 一眼树套树、 K-D 树、 CDQ 分治，但是假设我们除了莫队什么都不会，因为题目的空间是丧心病狂的 32.00MB（说你呢，丧心病狂的 20MB ＋强制在线的简单题）. 有两个约束条件如何莫队？某个金名金钩的大佬发了篇 O((N+M)NlogN)O((N+M)\sqrt Nlog N)O((N+M)N logN) 的所谓题解，但是这题本意完全不是这样，并且这个做法也只有卡常才能过。 本题如果用 O(1)O(1)O(1) 的时间复杂度单点增加或删除一个数、不大于 O(N)O(\sqrt N)O(N ) 的时间查询一个区间内的答案值就可以维持时间复杂度不变，我们只需要更新 cnt, 增加时如果以前没有这个数就按值域插入一个 1, 删除时如果现在没有这个数就设为 0, 最后移动完区间更新答案时求区间值。那么哪里有这样的 ds? 套值域分块模板即可。 Code:Code:Code: P4396 [AHOI2013] 作业 这题因为没有空间限制所以可以树套树、CDQ 分治、K-D 树。当然也可以从刚才那题的代码上改，新开一个分块存和就行了。2分钟过紫题我进国家集训队吧（其实系复制粘贴上一题然后改） Code:Code:Code: 结语 莫队其实练的还是基础的一些 ds 和做题的思路，比如我就复习了值域分块，学了 bitset 维护莫队等。应该很久之后才会更新了，不过没有树上莫队和莫队二离的话看这一篇足够了。能不能点个赞大佬们QvQ

🎯 ACGO 社区指南 欢迎来到 ACGO 社区！本文档将帮助你快速了解社区规则、赛事体系与常用资源，助你成为更优秀的算法选手。 > ⚠️ 重要提示 > 所有用户应遵守社区规则，共同维护公平、健康的学习环境。违规行为将按章处理。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📌 社区核心守则 类别 核心规则 重要链接 账号安全 妥善保管密码，不在公共设备保持登录 社区发言 禁止人身攻击、垃圾广告、恶意灌水 发帖规范 赛事诚信 禁止作弊、代刷、公开赛题答案 违规处罚细则 纠纷处理 建议使用「拉黑」功能，不公开引战 团队安全运营 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🏆 赛事 📖 赛事规则 * 巅峰排行榜规则介绍 * 排位分机制揭秘 * 公开赛申请指南 ⚖️ 违规处理机制 处罚标准： * 🚫 累计违规 > 3次：禁言30天 + 扣除竞赛分 * ⚠️ 累计违规 = 3次：禁言30天 * 📝 累计违规 < 3次：不予公示 重要说明： * 仅对挑战赛与排位赛前100名进行统一作弊核查 * 欢乐赛暂不纳入常规作弊核查范围 * 禁止在社区内公开发布天梯赛题目答案 * 对处罚有异议可通过[官方申诉渠道]申请复核 🙋 审核志愿者申： * 私信@AC君 ，需具备 CSP-J 复赛一等奖及以上资质。 相关规则： ACGO官方赛事公平审核规则 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💻 题库系统 🔧 使用指南 * 题目纠错：点击标题下方“题目纠错”按钮提交反馈，满10个有效纠错即可获得「BUG超度大师」勋章 * 题目申请：目前不支持个人题目申请进入官方题库 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 💬 讨论区指南 📝 内容创作规范 格式指南 * Markdown 语法教程 * LaTeX 数学公式语法 内容质量 * 提问的智慧 * 题解编写技巧 * 知识点精华贴 AI 工具使用 * AC助手使用指南 > 💡 创作建议：鼓励分享解题思路与算法分析，而非单纯发布答案代码。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👥 团队功能 🔄 团队管理 * 人员管理：团队安全运营公告与重要提醒 * 人数升级：通过私信联系 @AC君 申请 * 团队推荐：如何让你的团队登上推荐首页 * 商务合作：查看 ACGO团队TO B合作文档 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🛠️ 实用功能 🏅 勋章系统 * 勋章认证入口 * 部分勋章为趣味性质，可通过多次尝试获得 * 每累计10个有效题目纠错可获得「BUG超度大师」勋章 💻 编程环境 * Python IDE: Python 3.6 * C++ IDE: GCC 9.3.0 🐞 问题反馈 BUG反馈请提供以下信息： 1. 问题页面链接 2. 详细操作步骤 3. 浏览器版本信息 4. 错误截图或提示 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ❓ 常见问题 Q：账号被盗怎么办？ A：立即修改密码，检查是否有在公共设备未退出的情况。 Q：有人模仿我的名字怎么办？ A：如对方进行欺诈或骚扰，请保存证据并通过举报功能反馈。 Q：「码上开聊」栏目如何参与？ A：门槛为 CSP-J 复赛及以上奖项。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📚 资源中心 * 站务汇总 * 团队安全运营 * 知识点精华贴 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 最后更新：2025年11月27日 如有变更，以社区最新公告为准。

🎒 期末倒计时！你的玄学能量储备好了吗？ 在刷题、背诵、焦虑、抓狂的边缘反复横跳…… 别怕！期末许愿池2.0 限时返场！ 用宇宙的能量，换考场的奇迹—— ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌟 许愿通道正式开启 请严格按以下格式，留下你的神圣考前愿望： 🎯 我希望： __________ 💀 我愿意为此放弃： __________ 🔮 如果灵验，我将回来还愿并： __________ 🌟 优质示范： > 🎯 我希望： 数学期末考能稳定发挥，大题不崩 > 💀 我愿意为此放弃： 一周的峡谷夜游，专心刷题 > 🔮 如果灵验，我将回来还愿并： 在社区分享我的错题笔记+给AC君点爆100个赞 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 许愿者专属福利 所有按格式完整许愿的用户，均可参与能量池抽奖！ AC君将随机抽取 5位 天选锦鲤与点赞最高TOP1，送出AC狗拼图冰箱贴随机1片。 > ⏰ 活动时间：即日起 - 1月31日 23:59 > 🎉 开奖日期：2月2日（考完正好来还愿✨） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 许愿池使用说明 1. ✅ 愿望越具体、越真诚，宇宙接收信号越强！ 2. ✅ 放弃的代价要真实可执行（比如“放弃一周游戏”比“放弃呼吸”更靠谱） 3. ❌ 禁止许愿他人挂科（反向能量会反弹！） 4. 💫 互相点赞、评论加油的愿望，实现概率+99% ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🌌 来自宇宙的回复 > “你刷的每一道题，背的每一个知识点， > 都会在考场上变成让你稳住的底气。 > 许愿不是魔法，而是给自己一个仪式感的承诺—— > 期末考试月，我们一起把它变成奇迹发生的土壤。” ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👇 评论区已开放许愿通道，你的愿望，宇宙正在收听！ 转发给并肩作战的搭子，一起接收好运能量！ 🔮 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题

【团队安全运营公告】致各位队长：关于权限管理与团队安全的重要提醒 各位队长，大家好！ 为确保您团队的稳定与安全，ACGO 运营团队特此发布一则重要安全提醒。 一、核心原则：权限即责任，授权须谨慎 在 ACGO 团队系统中，队长及被授权的管理员所执行的操作（如移出成员、修改信息等），均被视为团队内部管理行为。平台尊重团队的自我管理权，因此不会对团队内部的权限使用进行干预或追责。 请注意：系统默认的“管理员”角色权限极高，不仅可以管理普通成员，甚至可以管理其他管理员。若您将“管理员”角色授予他人，对方理论上拥有与您近乎同等的权力。若授权不当，可能导致团队成员被误删甚至恶意清空。 二、行动指南：立即自查，防患于未然 我们强烈建议您立即执行以下操作，保护团队安全： ✅ 第一步：进入角色管理 * 在团队主页中，进入 “角色管理” 或 “权限设置”。 ✅ 第二步：审查现有权限 * 仔细检查每个角色（如“副队长”、“管理员”等）的权限设置。 * 重点核查是否有人拥有不必要的“移出成员”权限。 ✅ 第三步：取消高风险权限 * 对于非绝对信任的成员，请务必取消其“移出成员”权限。原则上，此权限应仅由队长本人持有。 * 修改后请点击保存。 ✅ 第四步：新建角色，按需授权（关键！） * 核心建议：如对成员没有绝对信任，请避免直接授予默认的“管理员”角色。 * 安全做法：点击 “新建角色”，自定义一个新角色，仅勾选完成任务所必需的权限（如发布公告、管理题目等），务必取消勾选“移出成员”、“管理管理员”等高危权限。 三、紧急情况处理 如您有确切证据表明团队遭遇以下情况： 1. 利用系统漏洞的恶意行为； 2. 因账号被盗引发的内部破坏； 请立即私信 @AC君 并提供证据，我们将介入协助核查。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 团队的安全，首要责任在于队长的谨慎授权。请像保管密码一样，谨慎管理团队权限。 感谢各位队长的理解与配合，让我们共同守护团队的和谐与稳定！

📢 【专项治理】讨论区净化 AC狗友们，在上次1024程序员节的社区互动中，我们收到了大量关于 “社区垃圾帖处理不及时” 的宝贵反馈。我们深知，随着社区用户和发帖量的快速增长，内容质量也面临着新的挑战。 为了能够共同营造一个更加纯净、优质、高效的氛围，我们将启动 “讨论区净化”专项治理行动。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🧹 行动细则：每周定期清理内容 从上周起，AC狗 已经开始重点针对以下几类内容进行清理： 1. 低质题解类 * 未使用 Markdown 进行规范排版的题解。 * 未使用 LaTeX 编写数学公式，影响阅读的题解。 * 仅有代码，没有解题思路、逻辑分析或注释的题解。 2. 无意义标题类 * 标题为无意义的乱码（如：uuu49hhi, tj, 6）或过于简单的词汇（如：AC, 题解），无法体现帖子内容的标题。 3. 不良互动类 * 内容为“挂人”、公开指责，但未提供确凿证据的帖子。 4. 版块错发类 * 本应发布在 「站务」 版块的社区功能建议、错误反馈等帖子。 为方便大家理解，以下是一些典型的待清理帖示例： （图示：无意义标题与低质内容示例） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们诚挚地邀请您，从下一次发帖开始： * 为您的题解配上清晰的思路。 * 用一个准确的标题，帮助更多人发现好内容。 * 使用 Markdown 与 LaTeX，让知识传递更优雅。 让我们携手，从每一个细节做起，一起将ACGO社区建设得更加美好！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 如何写好一篇题解？ > 规范使用 Markdown 排版

最近我也发现，在洛谷的题能进的题在ACGO里面却显示这样： 或者这样： 请官方看看是不是出题问题还是加大难度？请见谅。 不喜勿喷。

我们要做到： 积极攒卡筑卡组， 绿色游戏守准则。 直言漏洞促优化， 以礼待人敬对手。 我们还要做到： 不因阅兵失礼节， 不为烧绳拖战局。 不乱发表情滋扰， 不卡漏洞坏公平。

感觉Splay似乎也不难写，问题这两个的效率一直没个定论，FHQ-Treap常数应该会小一点但实际运行就难说了。而且好写程度和调试难度来说也有些不确定。有人建议一下吗？

7-1 二级 23 9 月）小杨的 X 字矩阵【矩阵构造题】 分数 25 作者 homework 单位 湖州学院 小杨想要构造一个 的 X 字矩阵（ 为奇数），这个矩阵的两条对角线都是半角加号 + ，其余都是半角减号 - 。例如，一个 5×5的 X 字矩阵如下： +---+ -+-+- --+-- -+-+- +---+ 请你帮小杨根据给定的 打印出对应的“X 字矩阵”。 输入格式: ⼀⾏⼀个整数 N（5≤N≤49，保证 N 为奇数）。 输出格式: 输出对应的“X 字矩阵”。 请严格按格式要求输出，不要擅自添加任何空格、标点、空行等任何符号。你应该恰好输出 N⾏，每⾏除了换⾏符外恰好包含 N 个字符，这些字符要么是 +，要么是 -。 输入样例: 在这里给出一组输入。例如： 5 输出样例: 在这里给出相应的输出。例如： +---+ -+-+- --+-- -+-+- +---+ 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB 栈限制

引言： 在每个游戏中，玩家们通常会使用一些“术语”来让交流更加方便，因此，学会“术语”是及其重要的。 <1>墙：指具有守护的单位。 <2>过墙：指通过某种手段去使敌方具有被守护的单位失去被守护。 <3>白板：指本身不具有任何技能或词条的单位。 <4>沉底：指某些关键牌一直抽不到。 <5>合模：指攻击力和防御力还行。 <6>亏模：指攻击力和防御力不行。 <7>超模：指攻击力和防御力很行。 <8>断水：指手牌过少。 <9>爆牌：指手牌过多。 <10>过牌：指使用卡牌去抽牌。 <11>卸牌：指手牌太多时打出大量手牌以保证不会爆牌。 <12>厚度：指使用卡牌以无中生有的方式去获得手牌。 <13>回手：指单位返回手牌。 <14>上线：指单位占领前线。 <15>卡线：指用单位一直占领前线。 <16>魔免：指具有“无法被敌方指令指向”的单位。 <17>otk：指“一回合斩杀”（One Turn Kill）。 <18>ttk：指“两回合斩杀”（Two/Three Turns Kill）。 <19>“守护”：指高威胁单位。 <20>剃头：指用战斗机攻击敌方总部。 <21>骗解：指舍车保帅，用不重要的单位替重要的单位挨解牌。 <22>疲劳：现指士气伤害。 <23>阅兵：或称作“月饼”，一种不文明游戏行为，指可以斩杀敌方时一直铺场，挑衅的一种。 <24>烧绳：一种不文明游戏行为，指一直拖时间，明明已经可以结束回合却一直等到强制结束回合。 <25>跳费：指获得额外的指挥点槽（每回合自动获得的那一个指挥点槽不算）。 <26>炸槽：一种古老的otk打法，指自己减少自己的指挥点槽。 <27>压槽：指减少敌方指挥点槽。 <28>贴膜：指让单位获得攻防上的加成。 <29>掀桌：指在对面有局面优势时解掉其所有单位。 <30>错斩：指指挥失误，导致本来可斩杀，但没完成斩杀。 <31>铸币：指指挥失误。 <32>终端：指某些卡组效果强劲，费用高的牌（如“英联邦”）。 <33>击剑：指好友对战。

WOC，点赞评论都炸了，榜二了 本蒟蒻还是搞不懂。在做一些高次的不等式的最值问题时，构造拉格朗日函数，求最值的一些注意事项？，以及解法，求教(各位能不能帮我刷刷热度，不然都没人看得见这条帖子) 原题：x²+y²=36,3x+4y的最大值(虽然柯西不等式也能做，但是我想用这种方法写)

我和“G.T.I.”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！ 邀请链接https://www.acgo.cn/application/2014558788447100928 对团队有贡献，有可能会职升。目前人少，前10名自动进入高管部门。 想拿的职位找管理员私聊就行了。欢迎大家加入团队并提出宝贵建议！ 玩三角洲的伙伴们，一起参加吧！

三小时死磕一道蓝题：从“这题是人做的？”到AC的狂喜 凌晨一点的书桌，屏幕亮得刺眼。ACGO的题库界面停留在一道蓝题上，标题旁的“难度：中等”像个嘲讽的笑脸。我盯着题目看了五分钟，脑子里只有四个大字：毫无思路。 本来只是想睡前刷道题放松下，哪成想，这一“放松”，就是三个小时。 这道题的题干不算长，大概是个区间查询的变种问题，要求在一堆杂乱的数据里，快速找出满足特定条件的子区间数量。起初我还挺轻敌，蓝题嘛，无非就是暴力优化一下，或者套个常见的算法模板。 我随手敲了个暴力枚举的代码，两层循环遍历所有区间，逻辑简单粗暴。点击提交，不出意外，TLE——时间超限。毕竟数据范围是1e5，暴力的O(n²)复杂度，跑断腿也过不了。 行，暴力不行就换思路。我翻出草稿纸，开始画样例的示意图。把数据一个个标上去，试图找出点规律。十分钟，二十分钟，草稿纸上画满了歪歪扭扭的线段和数字，还是一头雾水。我又试着把样例的答案拆解，反推每一步的计算逻辑，可总在某个节点卡住，前后矛盾。 “这题到底要考啥啊？”我抓了抓头发，有点烦躁。打开算法笔记，把滑动窗口、前缀和、单调栈这些可能相关的知识点翻了个遍，挨个往题目上套。套滑动窗口，发现条件不满足单调性；套前缀和，又不知道怎么转化问题。提交了两次修改版的代码，一次WA（答案错误），一次RE（运行错误）。 屏幕上的“提交失败”红得扎眼，我甚至开始怀疑：是不是我理解错题了？ 我强迫自己关掉代码编辑器，站起身去接了杯水。冷水泼在脸上，脑子清醒了点。回到座位，我没有急着敲代码，而是逐字逐句重读题干，把每一个条件都圈出来。“区间和”“最小值”“数量统计”……等等，区间和与最小值的结合？我猛地想起之前看过的一道类似题目，好像用到了单调栈+贡献法——计算每个元素作为最小值时，能贡献的合法区间数量。 对！就是这个方向！ 我瞬间来了精神，重新在草稿纸上梳理逻辑：先用单调栈找出每个元素左边和右边第一个比它小的元素位置，确定它作为最小值的区间边界；再结合前缀和快速计算区间和，判断是否满足题目要求。思路一旦通了，后面的步骤就顺理成章了。 我手指飞快地敲着键盘，定义数组、处理边界、维护单调栈、计算贡献……代码写得很顺，二十分钟就完成了初稿。这一次，我没有急着提交，而是自己造了几组数据测试，包括边界情况和极端数据。测试用例都过了，我心里有点小窃喜，但还是不敢掉以轻心——毕竟竞赛里，坑往往藏在细节里。 我又检查了一遍代码，果然发现了问题：计算区间和的时候，数据可能会溢出，忘记开long long了。“不开long long见祖宗”，这句竞赛圈的老话果然没说错。赶紧修改，把所有涉及求和的变量都改成long long类型。 深吸一口气，点击“提交”。 眼睛死死盯着屏幕上的加载进度条，一秒，两秒……当那个绿色的、带着金光的AC跳出来的时候，我差点叫出声。 凌晨四点零三分，距离我点开这道题，正好三个小时。 我瘫在椅子上，看着屏幕上的“通过所有测试点”，突然觉得刚才的烦躁、焦虑、挫败，都变成了一种难以言喻的快乐。这种快乐，不是刷水题时的轻松惬意，而是死磕到底后，拨云见日的酣畅淋漓。 其实竞赛刷题就是这样吧。没有谁是天生的神犇，不过是一道题一道题熬出来的。那些卡题的深夜，那些草稿纸上的涂鸦，那些一次次的提交失败，都是通往AC的必经之路。 关掉电脑的时候，窗外已经泛起了鱼肚白。我躺在床上，脑子里还在回放那道题的思路，嘴角却忍不住上扬。 明天，再去ACGO上挑一道蓝题？

非常猎奇，我们从此题洛谷题解可以发现，洛谷里AC的题解代码完全过不了样例，但本人题交后却能在洛谷AC（我抄题解不会吧制裁吧QAQ）。。。可是同样的代码放在ACGO却不行，原因可想而知，希望官方修改（（（ 本人只是听说这道题很凶残，所以过来看看，刚好发现题有问题 别尬黑（ @AC君 @༺དༀ༒∞░∞༒ༀཌ༻

致谢 @AI大模型(zhizang版) 灵感来源。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 由于主包暂时不知道期末日期，所以以下时间均用当天日期。 upd at 2026.1.30:现在知道了。 DAY −∞-\INFTY−∞ 科学一模，说是今天会出成绩，完力！就我那根依托的试卷我保证会被双打 （据说因为之前有些人作弊行为严重，所以我们的监考特别严格，特此记录。） 体育老师终于复活了，但为什么上来就让我们跑 1000m 啊，关键是我班前边几个 3'20'',3'10'',3',2'xx的究竟是什么怪物啊！ 累死了，明天还要语文一模和信息期末和英语一模……。 作业好多作业好多作业好多，能不能少点。 DAY −∞+1-\INFTY+1−∞+1 我们学校据说搞了一个什么科学提升计划，给那些在 A 线徘徊的人准备的。 巧了，现在 A 线和我还有些距离，虽然是负的。 好像就没什么特殊的了，今天食堂终于上玉米烙了，依旧一抢没，可惜我不能拍下那个场面了。 作业好多作业好多作业好多，能不能少点。 作业好难作业好难作业好难，干点人事吧。 DAY −∞+X-\INFTY+X−∞+X 不豪！我不小心在跑操的时候创倒了我们班的英语老师兼隔壁班班主任导致其骨裂（比骨折轻），回去休养了，由于她经常对隔壁班”施行暴政“，所以我喜提外号： > 民族英雄 DAY ∞+4→−4\INFTY+4 \TO -4∞+4→−4 学习，学习，学习。 作业好多作业好多作业好多，能不能少点。 作业好难作业好难作业好难，干点人事吧。 > 穿插：太好了今天某一科作业不用做我们有救了！ > 特殊事件：英语三模，有一个平时 110+/120110+/120110+/120（非作弊）的戈门被班主任判定为作弊+教唆他人作弊+传小抄喜提成绩归零+停课到期末，具体为什么这么干到现在都不知道，为其默哀三秒钟。 DAY −3-3−3 据说是因为我们班有些去培优班的（详见上文）不去了，所以伟大的 S(cience)T(eacher) 就让我去了，并使我的桌面整洁度 −n①-n^{①}−n①。 最后的动员，祝福等，回来学学学学学，抽个时间写一下邮寄。 要考试了，一切都要结束了。 我要何去何从？我问我自己。 注释 ①：一大堆试卷直接放在我的桌子上导致桌面整洁度 −n-n−n

https://www.acgo.cn/discuss/study/69663 貌似在 ACGO 上这样的题还不少（

嘿，大家。 想要首杀这题吗？ 请动用你们的小肝肝，小欧气，去挑战最后四个测试点吧！ 题解（想通过需要一点欧气）： #include <iostream> #include <algorithm> #include <vector> #define BUFSIZE 10000000 struct read { char buf[BUFSIZE], *p1, *p2, c; read(): p1(buf), p2(buf) {} char gc(void) { return p1 == p2 && (p2 = buf + fread(p1 = buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++; } read &operator >>(unsigned &x) { for (c = gc(), x = 0; c < '0' || c > '9'; c = gc()); } cin; struct write { char buf[BUFSIZE], *p1, *p2; write(): p1(buf), p2(buf + BUFSIZE) {} ~write() { fwrite(buf, 1, p1 - buf, stdout); } void pc(char c) { p1 == p2 &&(fwrite(buf, 1, p1 - buf, stdout), p1 = buf), *p1++ = c; } write &operator <<(long long x) { static unsigned stk[30], tp; } cout; unsigned n, s[500010][2], fail[500010]; unsigned val[500010], a[500010], p[500010]; namespace TT { unsigned rt, cnt, sz[1000010], csz[1000010], A[1000010], B[1000010], ls[500010], rs[500010], tp[500010]; unsigned s[500010], fa[500010], son[500010]; unsigned newnode(unsigned x) { unsigned u = x + n; csz[u] = sz[u] = 1, A[u] = B[u] = x; return u; } unsigned bd(unsigned x, unsigned y, unsigned p) { unsigned u = ++cnt; ls[u] = x, rs[u] = y, sz[u] = sz[x] + sz[y], tp[u] = p; } unsigned c[500010], cs[500010], ccnt; unsigned cbuild(unsigned l, unsigned r, unsigned p) { if (l == r) return c[l]; } unsigned build(unsigned x) { unsigned u = x; static unsigned tmp[500010]; } unsigned R[1000010], ct; void ini(unsigned x) { if (x > n) return A[x] = B[x] = R[x] = ++ct, void(); } void dfs(unsigned x) { static unsigned pt, f[500010]; f[pt++] = x, s[x] = 1, son[x] = 0; } void init() { cnt = 0; dfs(1); rt = build(1); ini(rt); } } std::vector<unsigned> vec[500010]; unsigned sz[500010]; void dfs(unsigned x) { sz[x] = 1; } long long ans[500010]; #define MAXN 2100010 unsigned cct, ls[MAXN], rs[MAXN], mn[MAXN], lmn[MAXN], cnt[MAXN], tag[MAXN]; long long sum[MAXN], stk[MAXN], tp; inline unsigned newnode(unsigned pos) { using TT::csz; unsigned u = tp ? stk[--tp] : ++cct; ls[u] = rs[u] = 0, tag[u] = sum[u] = mn[u] = 0, cnt[u] = csz[pos], lmn[u] = 2e9; return u; } inline void addtag(unsigned x, unsigned v) { sum[x] += 1ll * (v - mn[x]) * cnt[x]; mn[x] = tag[x] = v; } inline void pushdown(unsigned x, unsigned pos) { if (!tag[x]) return; } inline void pushup(unsigned x, unsigned pos) { using TT::csz; } inline void beats(unsigned &rt, unsigned v, unsigned pos) { if (!rt) rt = newnode(pos); } inline void lupdate(unsigned b, unsigned v, unsigned &rt, unsigned pos = TTrt) { using TTB, TT::R; } inline void rupdate(unsigned a, unsigned v, unsigned &rt, unsigned pos = TTrt) { using TTA, TT::R; } inline void update(unsigned a, unsigned b, unsigned v, unsigned &rt, unsigned pos = TTrt) { using TTA, TTB, TTR; } inline long long query(unsigned b, unsigned rt, unsigned pos = TTrt) { using TTB, TT::R; } void merge(unsigned &x, unsigned y, unsigned pos = TTrt) { using TTA, TT::B; } unsigned solve(unsigned x) { unsigned rt = 0; std::sort(vec[x].begin(), vec[x].end(), [&](unsigned x, unsigned y) { return sz[x] > sz[y]; }); } void solve() { cin >> n; } main() { unsigned T; cin >> T; } 好了，我的小肝肝已经不行了。你们加油！

假如地球只剩一分钟，你会干些啥？