666，这出题人是谁呀，直接抄了我们的著名的A+Bproblem！然后这事如何成为普及的？应该是入门呀，建议ac狗以后都把题目的难度筛一遍，别出现这种逆天题目。

3.141592653589793

ACGO欢乐赛第53场全题解\color{#FFC800}ACGO欢乐赛第53场全题解 ACGO欢乐赛第53场全题解 T1.早起 > 思路分析：判断小明是否迟到。周一到周五（星期1~ 5）需要7点及之前起床，周六周日（星期6~7）可以赖床。因此，如果今天是周一到周五且起床时间晚于7点，则输出YES（迟到），否则输出NO。 时间复杂度：O(1)时间复杂度：O(1)时间复杂度：O(1) 空间复杂度：O(1)空间复杂度：O(1)空间复杂度：O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2.小明的期末复习 > 思路分析：将复习时间D小时转换为外星时间单位。从最小单位开始逐级转换： > > 1. 小时数 = d % c > 2. 总天数 = d / c > 3. 剩余天数 = 总天数 % b > 4. 剩余月数 = (总天数 / b) % a > 5. 年数 = 总天数 / (a*b) 时间复杂度：O(1)时间复杂度：O(1)时间复杂度：O(1) 空间复杂度：O(1)空间复杂度：O(1)空间复杂度：O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3.小明的视疲劳回文串 > 思路分析：不区分大小写判断回文串。遍历字符串前半部分，将对应字符转为小写后比较： > > * 若s[i]与s[n-1-i]的小写形式不同，则需修改（计数+1） > * 当修改次数 ≤ m 时输出YES，否则NO 时间复杂度：O(n)时间复杂度：O(n)时间复杂度：O(n) 空间复杂度：O(1)空间复杂度：O(1)空间复杂度：O(1) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4.求奇数和 > 思路分析：奇数和=奇+偶。寻找： > > 1. 最大奇数（mx1） > 2. 最大偶数（mx2） > 若两者均存在，则和为最大值；否则输出-1。 时间复杂度：O(n)时间复杂度：O(n)时间复杂度：O(n) 空间复杂度：O(n)空间复杂度：O(n)空间复杂度：O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5.小明的斜线总和 > 思路分析：左上到右下的斜线特征：行号-列号为定值。用偏移数组D[K]存储斜线和（K=I-J+M-1保证非负）。遍历所有斜线求最大和。 时间复杂度：O(n×m)时间复杂度：O(n×m)时间复杂度：O(n×m) 空间复杂度：O(n+m)空间复杂度：O(n+m)空间复杂度：O(n+m) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6.小明和论坛发帖 > 思路分析：检查每个单词是否包含任意暴戾性子串。对每个单词S，遍历所有暴戾性字符串B[J]，若S.FIND(B[J])能找到子串，则标记为违禁词。 时间复杂度：O(n×m×L)时间复杂度：O(n×m×L)时间复杂度：O(n×m×L)（L为平均单词长度） 空间复杂度：O(m)空间复杂度：O(m)空间复杂度：O(m)（存储暴戾性字符串）

编译器为‌Microsoft Visual Studio me有点担心，所以找万能的网友们取取经 @NoonMaple，看老师用的是这个编译器，所以前来问一下。 窗口如下：

简单数数题。要是最后 30min 没写作业说不定就过了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意解析：定义一个长度为 nnn 的数组 AAA 的“峰”与“谷”如下： * 若 2≤i≤n2\le i\le n2≤i≤n 且 Ai−1<Ai>Ai+1A_{i-1}\lt A_i\gt A_{i+1}Ai−1 <Ai >Ai+1 ，则 iii 为 AAA 的峰。 * 若 2≤i≤n2\le i\le n2≤i≤n 且 Ai−1>Ai<Ai+1A_{i-1}\gt A_i\lt A_{i+1}Ai−1 >Ai <Ai+1 ，则 iii 为 AAA 的谷。 定义一个数组 AAA 为山峰数组当且仅当它的峰的数量严格大于谷的数量。 给定一个 nnn 的排列 AAA，求 AAA 有多少个子序列为山峰数组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们考虑什么情况下才是山峰数组。 注意到不算两边的话，一定是“...峰谷峰谷峰谷...”状的。 再进一步，分类讨论一下，可以发现一个长度为 kkk 的数组 BBB 是山峰数组当且仅当 B1<B2B_1\lt B_2B1 <B2 且 Bn−1>BnB_{n-1}\gt B_nBn−1 >Bn 。 现在问题就简单了。 先考虑暴力。 我们可以暴力枚举 i<j≤k<li\lt j\le k\lt li<j≤k<l 分别作为子数组的 B1,B2,Bk−1,BkB_1,B_2,B_{k-1},B_kB1 ,B2 ,Bk−1 ,Bk ，如果 Ai<AjA_i\lt A_jAi <Aj 且 Ak>AlA_k\gt A_lAk >Al ，则不论中间是啥，都可以构成山峰数组，对答案的贡献为 max⁡{2k−j−1,1}\max\{2^{k-j-1},1\}max{2k−j−1,1}（因为 j=kj=kj=k 时前面的是 12\frac{1}{2}21 所以要对 111 取最大值）。这样是 O(n4)O(n^4)O(n4) 的。 然后推式子。 ∑i=1n∑j=i+1n∑k=jn∑l=k+1n[Ai<Aj][Ak>Al]max⁡{2k−j−1,1}=∑i=1n∑j=i+1n[Ai<Aj]∑k=jn∑l=k+1n[Ak>Al]max⁡{2k−j−1,1}=∑j=2n−1∑k=jn(∑i=1j−1[Ai<Aj])(∑l=k+1n[Al<Ak])max⁡{2k−j−1,1}\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j}^n\sum_{l=k+1}^n [A_i\lt A_j][A_k\gt A_l]\max\{2^{k-j-1},1\}\\ =\sum_{i=1}^n\sum_{j=i+1}^n[A_i\lt A_j]\sum_{k=j}^n\sum_{l=k+1}^n [A_k\gt A_l]\max\{2^{k-j-1},1\}\\ =\sum_{j=2}^{n-1}\sum_{k=j}^n(\sum_{i=1}^{j-1}[A_i\lt A_j])(\sum_{l=k+1}^n [A_l\lt A_k])\max\{2^{k-j-1},1\}\\ i=1∑n j=i+1∑n k=j∑n l=k+1∑n [Ai <Aj ][Ak >Al ]max{2k−j−1,1}=i=1∑n j=i+1∑n [Ai <Aj ]k=j∑n l=k+1∑n [Ak >Al ]max{2k−j−1,1}=j=2∑n−1 k=j∑n (i=1∑j−1 [Ai <Aj ])(l=k+1∑n [Al <Ak ])max{2k−j−1,1} 显然我们可以通过树状数组 O(nlog⁡n)O(n\log n)O(nlogn) 预处理出 ∑j=1i−1[Aj<Ai]\sum_{j=1}^{i-1} [A_j\lt A_i]∑j=1i−1 [Aj <Ai ] 与 ∑j=i+1n[Aj<Ai]\sum_{j=i+1}^{n} [A_j\lt A_i]∑j=i+1n [Aj <Ai ]，分别记作 prei,sufi\text{pre}_i,\text{suf}_iprei ,sufi 。则原式为： ∑i=2n−1∑j=inpreisufjmax⁡{2j−i−1,1}\sum_{i=2}^{n-1}\sum_{j=i}^n\text{pre}_i\text{suf}_j\max\{2^{j-i-1},1\}\\ i=2∑n−1 j=i∑n prei sufj max{2j−i−1,1} max⁡\maxmax 有点难搞，拆开吧。 ∑i=2n−1preisufi+∑i=2n−1∑j=i+1npreisufj2j−i−1\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j2^{j-i-1}\\ i=2∑n−1 prei sufi +i=2∑n−1 j=i+1∑n prei sufj 2j−i−1 然后继续转化。注意到 222 的整数次幂是可逆的。所以： ∑i=2n−1preisufi+∑i=2n−1∑j=i+1npreisufj2j−i−1=∑i=2n−1preisufi+∑i=2n−1∑j=i+1npreisufj2j2i+1=∑i=2n−1preisufi+∑i=2n−1prei2i+1∑j=i+1nsufj2j\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j2^{j-i-1}\\ =\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\sum_{j=i+1}^n\text{pre}_i\text{suf}_j\frac{2^j}{2^{i+1}}\\ =\sum_{i=2}^{n-1}\text{pre}_i\text{suf}_i+\sum_{i=2}^{n-1}\frac{\text{pre}_i}{{2^{i+1}}}\sum_{j=i+1}^n\text{suf}_j2^j\\ i=2∑n−1 prei sufi +i=2∑n−1 j=i+1∑n prei sufj 2j−i−1=i=2∑n−1 prei sufi +i=2∑n−1 j=i+1∑n prei sufj 2i+12j =i=2∑n−1 prei sufi +i=2∑n−1 2i+1prei j=i+1∑n sufj 2j 我们只需要递推求出 ∑j=i+1nsufj2j\sum_{j=i+1}^n\text{suf}_j2^j∑j=i+1n sufj 2j 即可。 代码如下： 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)。

> 祝大家新年快乐！ 众所周知，在做游戏时，需要用到许多例如： * 清屏 * 改变颜色 * 关机？ * 消息提示框 甚至创建窗口应用。 但是，许多人不会，那么我就为大家讲解一下。 > 部分内容来自网络 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1.清屏 清除所有输出。 使用system 函数。 需包含cstdlib.h 头文件。 该函数原型：int system(const char *command); ，用于运行cod命令。 参数：const char *command 是传入的系统命令字符串，Windows下传cmd命令、Linux/macOS下传shell命令；传NULL时，用于检查系统是否有可用的命令处理器。 返回值：int 类型，返回值结果依赖操作系统，执行成功通常返回命令的退出状态码，执行失败（如无命令处理器）返回非0值。（其实没什么用） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 那么，众所周知，在cmd中，cls 指令用于清屏。 所以，清屏指令为：system(“cls”); 2.设置字体颜色（全屏） 设置背景颜色，字体颜色 仍然使用system 函数。 在cmd中，设置颜色指令： color [前景色代码][背景色代码] 代码表： 0=黑、1=蓝、2=绿、3=浅绿、4=红、5=紫、6=黄、7=白、8=灰、9=淡蓝、A=淡绿、B=淡浅绿、C=淡红、D=淡紫、E=淡黄、F=亮白 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 事例： 设置背景红色，字体黄色 3.设置标题 在弹出的控制台中，最上方的标题一般默认为C:\…或D:\… 这类，即exe文件地址。 但是，这样看上去非常丑，且无法表达主题。 使用system 设置标题。 cmd代码： 事例： 运行后，标题设置为“这是一个标题吗” 4.等待 使用Sleep 函数，需包含Windows.h 头文件。 函数原型：DWORD Sleep(DWORD dwMilliseconds); 说明：参数dwMilliseconds为休眠毫秒数，返回值固定为 0，无失败返回值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 注意，1000毫秒=1 秒，因此休眠1秒写作：Sleep(1000) . ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 破100阅读，5赞出窗口应用

这段代码有什么问题？ '''cpp '''cap #include <bits/stdc++.h> using namespace std; int main() { int n, a[105][105], num = 1; cin >> n; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) a[i][j] = num; num ++; } for (int i = 1; i <= n; i ++) { if (i % 2 == 0) { int b[105]; num = 1; for (int j = n; j > 0; j --) { b[num] = a[i][j]; num ++; } for (int j = 1; j <= n; j ++) a[i][j] = b[j]; } } for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) cout << a[i][j] << " "; cout << endl; } } '''

题目大意：一个矩阵，处理后最外圈顺时针转90°，往里一圈变为逆时针转90°，再进去再变回顺时针......以此类推 > 非完整代码： 思路：先分析是在矩阵的第几层，然后再按照顺时针或逆时针方向进行指定旋转的操作，从数组A中转移到B中，最后输出。

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

比赛结束！帖子封存！！！给后人考古！！！ 好像太简单了，下一场给大家上点强度 估计是播报不了了，本人不知道我也看不了榜，大家加油。 本帖是ZZSR #1的赛时答疑帖。仅允许在赛时提出与题目描述有关的问题。禁止灌水，禁止发做法。违者取消奖励资格。 赛时播报区： * ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 问题 回答/修复情况 ？ T1不是选择来洗，是每张牌都洗 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大样例 点此下载大样例 提取码: RSZZ

LHCX Cup 2026（邀请码：Rped） 岚核 这里是综合目录，各个链接如下： * 赛事讨论帖 * 题解贴 * 获奖通知贴

NOIP太难了，怎么一堆神犇，等我考上广附或者华附或者广外或者没开挂省实或者正常点的二中六中广雅执信铁一我一定不会废成这个样子 前言 整体二分和 CDQ 分治是与莫队并列的三大离线算法，本质都是分治，不过思想和使用范围不同，通常可以高效解决平衡树套线段树、BIT套主席树这些编码难度较大的问题。它们较少在 NOIP 和 CSP 中考察，同时难度也较大（模板题紫），但是可以多做几道紫题不过有助于增进对分治的理解。 第一部分：整体二分 整体二分是一种离线算法。 （说了=没说） > 可以使用整体二分解决的题目需要满足以下性质： > 1.询问的答案具有可二分性 > 2.修改对判定答案的贡献互相独立，修改之间互不影响效果 > 3.修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关 > 4.贡献满足交换律，结合律，具有可加性 > 5.题目允许使用离线算法 > ——许昊然《浅谈数据结构题几个非经典解法》 整体二分格式：整体二分函数中通常有4个参数，表示答案值域 [L,R][L,R][L,R] 和所执行的操作/询问的范围 [l,r][l,r][l,r] 。函数先计算出 LLL 和 RRR 的平均值 midmidmid ，用二分思想猜测 midmidmid 为答案，并使用数据结构（99%是BIT和线段树）检验每个询问的答案小于 midmidmid 还是大于 midmidmid ，小于 midmidmid 的分到左组，大于 midmidmid 的分到右组，分别解决，将两个组的答案值域范围缩小一半。当答案值域大小为1时（L=RL=RL=R）将该组所有询问的答案设为 LLL(RRR) 并返回。 更细致的讲解将在例题中展现，最详细的在后文 Dynamic Rankings 一题的讲解中 区间第 K 小 在上一篇关于主席树的文章中我们用主席树实现了区间第 kkk 小的查询，这里我们使用复杂度略高的整体二分尝试实现。 先从一个问题入手： 如果只有一次查询，我们要如何解决？ 答案很明了：排序二分。我们把所有数从小到大进行排序（不是区间内，并且排序时记录原来的位置），然后使用二分每次猜一个位置 midmidmid ，如何判断答案在 midmidmid 的左边还是右边？我们使用树状数组BIT，对于所有在 [l,mid][l,mid][l,mid] 的数，我们在它原来的位置加一，最后计算在询问区间 [l,r][l,r][l,r] 中有多少个一（也就是求和），就可以知道答案在 midmidmid 左边还是右边了。如果数量小于 kkk ，说明答案猜小了，需要增加 midmidmid 使统计到的数量增大（统计到的数量其实代表在询问的区间 [l,r][l,r][l,r] 内有多少个数小于 a[mid]a[mid]a[mid] ，第 kkk 小值在区间 [l,r][l,r][l,r] 内应有 k−1k-1k−1 个数小于它）否则，缩小 midmidmid 。 小技巧：当答案大于 midmidmid 时，我们将 lll 设为 midmidmid ，将 kkk 减去 midmidmid ，这样就可以减少很多计算量。 如图所示： 时间复杂度为 O(Nlog2N)O(Nlog_2N)O(Nlog2 N) 那么如何求解多个询问呢？ 注意到每次询问都查验了一个 midmidmid ，那我们对所有询问查询区间值，然后得出它在 midmidmid 左边还是右边，分成两组分治完成不就行了吗？ 然后就 AC 了 参考代码：我没写，可以在 OI-Wiki 中查看。 这个代码真难懂，加点注释罢~ 可过P3834 注意：memset单次复杂度为 O(N)O(N)O(N) ，会炸，所以对于每一个+1操作，我们在原来的位置-1就行了 总复杂度为 O(Nlog2O(Nlog_2O(Nlog2 2N)^2N)2N) ，请读者自己证明 把算法讲清楚实在是太难了，请对照代码理解，初学者怎么都懂不了的请移步左神的整体二分 基本用法 首先可以静态做出我们讲过的 P4137 Rmq Problem / mex ，解法不细讲因为代码没写而且只是蓝题，可以在阅读完全文后自行思考或者参考题解 接下来正经讲讲题 带修改区间第 KKK 小 首先考虑主席树。 这题不能用普通主席树，需要用BIT套主席树实现修改操作，本质是用树状数组思想 O(log2N)O(log^2N)O(log2N) 修改权值线段树的其中一个版本，询问时用 O(log2N)O(log^2N)O(log2N) 求出区间内的线段树权值和并递归询问。 此题也可用整体二分。 我们把询问和修改操作统称为操作一起二分。 这时我们要用不同写法的整体二分了。不使用排序，二分答案可能的权值（即最小值到最大值），再遍历所有数，把大小小于 midmidmid 的插入树状数组。 我们更改一下结构体的结构，有一个标记 op 表示操作类型， op=1 意味着查询， op=2 意味着将一个数值插入树状数组。当 op=1 ， x 意为查询的 lll ， y 表示查询的 rrr ， k 表示查询第 kkk 小， id 表示查询的编号，用于输出答案。当 op=2 ，意为将第 x 个位置改为 y 并在 BIT 的第 x 位增加 k 。 k=1 表示插入一个数， k=-1 表示删除一个数。 接下来把修改操作拆分为一个删除操作和一个插入操作。插入操作：在第 x 个位置添加一个数 y ，其 k=1 ，用于查询；但是我们有时需要修改，添加一个删除操作， x 和 y 与要删除的操作一致，这样当被删除的操作被执行时这个操作也会执行，上个操作在 BIT 的 x 位+1，这个操作又在 BIT 的 x 位-1，二者抵消。删除完了重新插入， x 相等， y 为修改后的值， k=1. 注意到不用初始化，可以将初始化操作全部转化为插入操作。 所有操作一起进行二分。由于y为插入操作插入后的值，如果 y>midmidmid ，这个操作对答案没有影响（因为你的 BIT 只计算小于 midmidmid 的数），分到右组（只有更大的 midmidmid 查询才会用到这个操作，所以去右组等更大的midmidmid），否则在 BIT 中实现这个插入/查询操作，并分到左组等更小的 midmidmid. 最后，如果 l=rl=rl=r ，将该组所有查询操作答案设为 lll 并返回。 有的人可能会疑惑：你要怎么保证每个查询刚好在且仅在它前面所有操作执行完后执行呢？即，你怎么保证执行是按时间顺序的呢？答：你按时间顺序挨个加入操作，分治的分组是从左到右遍历的，并不会改变同一组内两个操作的顺序，你在遍历到修改操作时立刻修改，遍历到查询操作就立刻查询，可以保证其有序性。 虽然比较难理解，但是代码是很透彻的，做整体二分一定要多看代码，弄清每一个细节，这样就能轻松理解。 Code:Code:Code: 注意这里把答案先初始化为-1，如果不是-1说明是有答案的，对这个答案进行输出，实际有更简便的写法，见后文。 该代码复杂度： O(NlogNlogV)O(NlogNlogV)O(NlogNlogV) 所用时间：最长运行测试点197ms，使用 O2 优化21个测试点总时长2.08s 其它解法：树套树、分块 整体二分因为用的 BIT ，加上没有大量递归，常数较小，是不错的选择。 二维第 KKK 小 题目看这里： P1527 [国家集训队] 矩阵乘法 很明显可以用二维 BIT 的单点修改+区间查询完成，其实并不难，套用模板即可。注意这里使用了基础写法 Code:Code:Code: （排序写法，初学者较容易理解） 注意该题复杂度为 O(N2log3N)O(N^2log^3N)O(N2log3N) ，最大一个点247ms 此题其它解法： CDQCDQCDQ 分治（O(N2log2N)O(N^2log^2N)O(N2log2N)，好像是吧）、权值线段树套小波树（WaveletTreeWavelet TreeWaveletTree)，时间复杂度 O((N2+Q)log2N)O((N^2+Q)log^2N)O((N2+Q)log2N) 、小波矩阵（WaveletMartrixWavelet MartrixWaveletMartrix)套小波矩阵，时空复杂度 O((N2+Q)log2N)−O(N2logN)O((N^2+Q)log^2N)-O(N^2logN)O((N2+Q)log2N)−O(N2logN) 线段树维护整体二分 P3332 [ZJOI2013] K大数查询 注意到不能用普通 BIT 进行整体二分插入了，需要一种区间插入数据的数据结构。 没错！变体 BIT线段树。 其实也就是换了一个方式实现。由于是线段树，我们不需要一个一个操作清空，而是直接用基础区间增加 d 和区间设为 d 的线段树，每次操作前给整个区间（节点1）打上清空 tag 就行啦。 注意到分治代码略有不同，这是因为求的是第 kkk 大 Code:Code:Code: 注意 tag1 是增加 tag2 是清空 时间复杂度 O(Nlog2N)O(Nlog^2N)O(Nlog2N) (因为题目有特殊约定），但是由于是大常数的线段树，最大一个点跑到了273ms。唉！ 同时此题还有平衡树套线段树（应该是 O(Nlog3N)O(Nlog^3N)O(Nlog3N) 吧，常数挺大，一般加标记永久化才可过)、BIT套主席树（O(Nlog2N)O(Nlog^2N)O(Nlog2N)，常数较大，可用标记永久化)、分块（O(NNO(N\sqrt NO(NN )等解法。 下集预告 你信心满满地去洛谷搜整体二分的题，搜到了这个东西： 动态逆序对 然而，你很快发现，这道题不能用整体二分（这里指普通整体二分） 它属于另一个领域： CDQ分治CDQ分治CDQ分治 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ToToTo bebebe continuedcontinuedcontinued<−<-<− 附：不知道为什么流量很少而且好像 ACGO 数据问题目前阅读量和回复数莫名一致的第二篇 没人看的第三篇

本篇包含树上主席树、可持久化并查集、CDQ 分治套 CDQ 分治、CDQ 分治优化 DP 等内容，例题都是知识点的进阶，请在知识点基础上学习。 第一篇 第二篇 该系列已加入洛谷保存站大套餐。 第三部分（续） 2.树上主席树模板 P2633 Count on a tree 不用看题，树上链第 kkk 小。 这道题乍一看又像是树链剖分又像是主席树。 实际上是一道极好的主席树例题，可以先想5分钟正解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎回来。 其实很简单。看到是离线就知道不能树上整体二分，考虑主席树。注意到主席树是一种“可加”的数据结构，可以通过差分和前缀和计算区间，对于树上链条要怎么计算前缀和？将新版本的权值线段树建立在父亲节点的树上即可，计算时使用树上差分，将 uuu 版本的节点值加 vvv 版本的节点值再减去 LCA(u,v)LCA(u,v)LCA(u,v) 版本的节点值和 faLCA(u,v)fa_{LCA(u,v)}faLCA(u,v) 版本的节点值即可得到链上的权值线段树某个节点的节点值。其它的按照标准的主席树差分求第 kkk 小值编码即可。还是能用到树链剖分，不过是用来求 LCA 的（LCA 肯定是树剖最快啊，怎么会有人用树上倍增呢）。代码中在 dfs1 中建主席树的版本。 Code:Code:Code: 时间复杂度： O((M+N)logN))O((M+N)logN))O((M+N)logN)) 3.P2468 [SDOI2010] 粟粟的书架 还是有一定难度的。 这次没写最优解主席树，而是写了整体二分（没忍住）。 标准做法是当作二合一题做，后半是主席树二分的模板，索引为从大到小排序的书本厚度，二分需要拿的最薄的书籍，如果左节点足够厚就递归左节点，否则递归右节点。前半部分大部分题解用了毫无美感（暴论）的二维前缀和+二分，枚举权值 ppp，维护 (1,1)(1,1)(1,1) 到 (i,j)(i,j)(i,j) 的矩阵大于等于 kkk 的数的总和以及这个矩阵中大于等于 kkk 的数的个数并二分，利用 0≤pi,j≤10000\leq p_{i,j}\leq 10000≤pi,j ≤1000 的特殊性质用 O(RCmax{pi,j})O(RCmax\{p_{i,j}\})O(RCmax{pi,j }) 的时间复杂度卡过第一问，也有一些神犇优美地用二维差分主席树解掉达到所有点 O(RClog2(RC))O(RClog_2(RC))O(RClog2 (RC))的时间复杂度，值得学习👍。 但是我们不用主席树。注意到这题和国家集训队的矩阵乘法那题很像，可以从厚到薄排序然后用整体二分解决。只需要在整体二分中累加答案即可，分到右组时加上需要添加的书籍数量，甚至不用写两份代码，准备两个大小不同的树状数组即可。注意整体二分的二分与一般二分不同，找第一个不符合的值域（或下标）时要特判，如图： 时间复杂度每个点都是 O(RClog2(RC))O(RClog^2(RC))O(RClog2(RC)). Code:Code:Code: 4.水题：P7424 [THUPC 2017] 天天爱射击 肥肠简单，请先自行构思。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如果把每个子弹当作询问的话，处理射击后的每个木板的状况会很麻烦。考虑整体二分，综上所述只能把木板当作询问，直接二分第几发子弹射出后木板破碎，这就在树状数组的解决范围内了，统计对每个木板来说 midmidmid 发子弹发出后有多少打在这个木板区间内即可 check.最后确定答案时，把贡献算在最后这发打坏木板的子弹上就行了。小 Trick: 整体二分时将值域加一，这样完成不了的询问就会落在值域加一的答案区间，这题中可以将这些答案忽略掉因为加到第 m+1m+1m+1 个子弹的答案不算数（只有 mmm 发）不会输出。 Code:Code:Code: 时间复杂度： O((N+M)log2M)O((N+M)log^2M)O((N+M)log2M) 5. 一道毒瘤来啦！ P9175 [COCI 2022/2023 #4] Mreža 依旧 COCI. 自行看题。 有不同做法，这里采用时间复杂度最优的算法。可以使用 P2633 的树上主席树技巧，转化为树上主席树二分。首先将 viv_ivi 和 sis_isi 共同离散化（就是因为一不小心离散化了两个后面才没 WA,纯运来的，实际上这一步不是必要的）以 viv_ivi 为下标建立权值线段树，叶子节点值为 cic_ici ,维护每个 viv_ivi 区间的 cic_ici 总和，如果预算够就往右递归，否则往左递归。除此以外，单独计算链上 sis_isi 最小值，取这两个答案的最小值即可。 可以用树上 ST 表求解链上最小值，设 fai,ufa_{i,u}fai,u 为节点 uuu 向上 2i2^i2i 个祖先，sti,ust_{i,u}sti,u 为从节点 uuu 向根节点延伸的长度为 2i2^i2i 的链上的最小值，有： sti,u=min(sti−1,u,sti−1,fai−1,u)st_{i,u}=min(st_{i-1,u},st_{i-1,fa_{i-1,u}}) sti,u =min(sti−1,u ,sti−1,fai−1,u ) 区间的合并如图所示： 然后像倍增 LCA 一样先让低的跳，如果一个是另一个的祖先就返回，否则一起跳，跳到 LCA 的下一层，最后再跳 LCA 这层即可。 时间复杂度：O((n+q)log2n)O((n+q)log_2n)O((n+q)log2 n) 目前无特意卡常跑进除隐私保护外第6优解，但是离散化了还没跑过卡常+没离散化的某篇题解，之所以题解可以不用离散化是因为主席树动态加点只会给 update 过的节点开空间，其它空间不会浪费，因此空间开到 O(nlog2V)O(nlog_2V)O(nlog2 V) 即可。 Code:Code:Code: 6.P3402 【模板】可持久化并查集 这题很罕见地考模板不强制在线，导致题解区有很多离线的 O(Nlog2N)O(Nlog_2N)O(Nlog2 N) 做法，如果想练习可持久化并查集请自觉 （不是）。 首先，可持久化数据结构不可以用任何均摊，所以合并不能使用路径压缩，可以用时间复杂度稳定为单次 O(log2N)O(log_2N)O(log2 N) 的按秩合并进行合并。按秩合并采用高度法，将高度小的数作为高度大的树根的儿子。用主席树维护 fa 数组和 dep 数组的更改。注意这里一次修改要开两条链，一条连向 fa 更新的叶子节点一条连向 dep 更新的叶子节点，因为按秩合并时 fa 头儿子 dep 头爸爸。每次修改都进行一次主席树操作，时空复杂度 O(Nlog2N)O(Nlog^2N)O(Nlog2N). Code:Code:Code: 各种函数意义看英文字面意思。pos 函数是辅助按秩合并的，它返回某个版本第 k 个元素在动态开点的主席树内的编号。 CDQ 分治进阶 7.P3769 [CH弱省胡策R2] TATT 直到做完这道题都不知道题目是什么意思 四维空间最长上升子序列。需要 CDQ 分治套 CDQ 分治和 CDQ 优化 DP 的技巧。 这里先说 CDQ 的顺序。对于 cdq2 函数，定义 cdq2(l,r) 意为计算 [l,mid][l,mid][l,mid] 区间对 [mid+1,r][mid+1,r][mid+1,r] 区间元素的贡献。按照 DP 从左到右的顺序，先分治左半部分的区间，计算好左半部分的答案，再计算左半部分对右半部分的贡献，最后分治右半区间计算右半部分内部互相的贡献。DP 计算用树状数组即可。 但是这是四维空间，要怎么用 CDQ 分治呢？可以用 CDQ 套 CDQ，一个 CDQ 解决第二维，嵌套另一个 CDQ 解决第三维。先回顾三维 CDQ:排序解掉第一维，左右子区间内部排序确保有序性然后双指针解决第二维，数据结构解决第三维。四维时如何确保第一维的有序性？注意到永远是第一维小的向第一维大的元素贡献答案， 可以在第一个 CDQ 中先计算左区间，然后（此时左边的第一维比右边的小）把左边的所有元素打上标记0，右边的打上1，再排序第二维，进入 cdq2,cdq2 中先计算左组，再将左右分别按第三维排序，双指针遍历，左区间该元素的标记为0则插入树状数组，右区间该元素的标记为1则计算答案，（所有被打上0的元素第一维都比所有打上1的小）完事清理树状数组并将右区间按第二维排序递归计算右区间。 于是能过矣。 注意到当双指针过后，DP 的值受到改变，树状数组清除时不知道该减去多少，不过插入树状数组的位置（第四维度的值）还存着，对于每个位置，树状数组把这个位置的数直接设为0即可。由于每次是计算区间 [1,x][1,x][1,x] 的 DP 最大值，树状数组是可以的。 时间复杂度：O(Nlog3N)O(Nlog^3N)O(Nlog3N) 记得依旧查重。 Code:Code:Code: 8.P4849 寻找宝藏 比较难的题。 CDQ 套 CDQ 的部分不讲了（这里给出的 CDQ 代码略有不同，不过意思是一样的，自己想），我们来讲讲 DP. 下文的长度表示最长上升子序列长度。计算 iii 结尾的方案数，我们遍历 jjj 符合条件的 dpjdp_jdpj 值，如果 iii 目前的最长子序列长度小于 jjj 计算的长度值，将 iii 的最长子序列长度和方案数设为当前 jjj 的值（很好理解），如果恰好相等，说明又有一种方法达到当前的 dpidp_idpi 值，将方案数加上当前遍历元素的方案数（也很好理解）。树状数组计算时也按这个思路统计答案，最后直接返回计算到的答案，修改时如果当前位置的长度小于插入值的长度就设其为插入值的长度，相等则累加方案数。为什么正确？DP 式中需要的是长度的最大值，由于树状数组每个元素存储的是一个区间内的元素信息，可以把不同区间的答案合并。 时间复杂度： O(Nlog3N)O(Nlog^3N)O(Nlog3N) Code:Code:Code: 9.P5621 [DBOI2019] 德丽莎世界第一可爱 毒瘤，和上题差不多，只不过值域有负数和零。查重和树状数组的部分有不同，答案初始是 -INF，并取 sz 的最大值；去重合并同类项时如果贡献是负数就不累加；树状数组初始化和删除是 -INF.时间复杂度懒得打了一模一样。 10.P2487 [SDOI2011] 拦截导弹 前一问和寻找宝藏差不多，只不过是三维的。注意树状数组要统计更大值（看题！），所以树状数组的索引用 m−aiv+1m-a_{i_v}+1m−aiv +1.双指针的判断部分也是反的。 第二问：反着计算最长上升子序列长度和方案数。将 ididid 和 aiva_{i_v}aiv 倒过来，aiha_{i_h}aih 取相反数然后再跑一遍 CDQ 就行了。接下来可以把值域这样把两个答案并在一起（加在一起再减去重复计算的当前元素，也就是说-1），如果等于全局最长上升子序列长度就说明是方案的一部分，两个答案的方案数相乘即是贡献的方案数，最后除以全局最长上升子序列的方案数得到概率；否则输出0（不在最优方案中）。O(Nlog2N)O(Nlog^2N)O(Nlog2N). Code:Code:Code: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大抵不会再更新了。

好难

有帅哥美女能公布一下今年NOIP的四道题解吗(要AC的)

1.https://excalidraw.com/ 一个2D画图网站，牢夏推荐，支持多种格式图片编辑 2.https://ggb123.cn/3d 当你画2D图画乱了可以尝试这个，这是个3D画图工具！而且支持数学代数工具和手动画图工具 3.https://www.jyshare.com/front-end/8006/ 文本对比工具，当你代码有找不到的地方时可以用 如果有其他网站的话可以推荐给我

Markdown 的目标是实现「易读易写」，成为一种适用于网络的书写语言。因此acgo普遍使用 Markdown 发布内容。 请仔细阅读下列文档，如果没有按照要求正确使用格式，将可能无法发出讨论，或者被删除。 段落和换行 一个 Markdown 段落是由一个或多个连续的文本行组成，它的前后要有一个以上的空行。普通的 Markdown 段落不可以用空格或制表符来缩进。 空行：一行之内只包含回车换行、空格、制表符。 标题 Markdown 的标题是在行首插入 1 到 6 个 #，# 和标题文字之间使用一个或多个空格，对应到标题 1 1 到 6 6 级。 例如： 这是 H1 这是 H2 这是 H3 这是正文 显示的效果如下： 标题与正文 警告 不要全文使用标题，或者用标题强调特别多的文字。这会让读者觉得困扰。 强调 Markdown 使用星号（*）和底线（_）作为标记强调字词的符号，被 * 或 _ 包围的字词会被转成用 <em> 标签包围（即斜体），用两个 * 或 _ 包起来的话，则会被转成 <strong>（即粗体）。 例如： 单星号斜体 单下划线斜体 双星号加粗 双下划线加粗 删除线 显示的效果如下： 单星号斜体 单下划线斜体 双星号加粗 双下划线加粗 删除线 但是如果你的 * 和 _ 两边都有空白的话，它们就只会被当成普通的符号。如果要在文字前后直接插入普通的星号或底线，你可以用反斜线（\）（参见下面的“反斜杠”部分）。 例如： *使用反斜线开头的*被当做是普通的字符* 显示的效果如下： 使用反斜线开头的被当做是普通的字符* 代码块 如果要发送代码，但没有按照下面的方式进行格式化，将不能发送成功。 大段代码 Markdown 建立代码块的方法：将 置于这段代码的首行和末行，独立成一行。第一行的 后面可以加上语言名称，例如 cpp、java、c、pascal 等（不要写成 c++）。 例如： C++代码示例 #include<iostream> 小段代码 需要引用代码时，如果引用的语句只有一段，不分行，可以用 ` 将语句包起来。 注：如果你真的要打 这个字符的话，可以仿照和 * 这个字符一样的处理方式，在 前加一个反斜杠。 区块引用 Markdown 标记区块引用的方法是在行的最前面加 >，也可以只在整个段落的第一行最前面加上 >，区块引用内部可以嵌套，只要根据层次加上不同数量的 > 即可，引用的区块内也可以使用其他的 Markdown 语法，包括标题、列表、代码区块等。 例如： > Markdown 标记区块引用的方法是在行的最前面加 >。 > > 也可以只在整个段落的第一行最前面加上 >。 > > > 区块引用内部可以嵌套，只要根据层次加上不同数量的 > 即可。 > > > > 我是内部嵌套区块，我可以使用其他 Markdown 语法哦。 > > > > > > 我是引用区块内使用 3 级标题语法。 显示的效果如下： Markdown 标记区块引用的方法是在行的最前面加 >。 也可以只在整个段落的第一行最前面加上 >。 区块引用内部可以嵌套，只要根据层次加上不同数量的 > 即可。 我是内部嵌套区块，我可以使用其他 Markdown 语法哦。 我是引用区块内使用 3 级标题语法 //在引用区块内可以加入代码块 import java.net.URL; import java.util.Arrays; import java.util.Date; import java.util.Set; 列表 Markdown 支持有序列表和无序列表，无序列表使用星号、加号或是减号作为列表标记，有序列表则使用数字接着一个英文句点。两种列表方式格式都是：列表标记 + 空格 + 列表项，即列表项目标记通常是放在最左边，也可以缩进最多 3 3 个空格，项目标记后面则一定要接着至少一个空格或制表符。 1 无序列表 星号、加号或是减号三种列表方式效果等同。 例如： * Red * Green * Blue * Red * Green * Blue * Red * Green * Blue 它们的显示效果均为： Red Green Blue 2 有序列表 有序列表则使用数字接着一个英文句点。 例如： 1. Red 2. Green 3. Blue 显示效果为： Red Green Blue 链接 在方块括号后面紧接着圆括号并插入网址链接即可，如果你还想要加上链接的 title 文字，只要在网址后面，用双引号把 title 文字包起来即可，例如： 行内式链接标题 显示效果：这是 行内式链接标题 内联方式。 图片 Markdown 使用一种和链接很相似的语法来标记图片。在互联网上发表含有图片的内容时，需要将该图片上传至可公开访问的存储空间内（也就是俗称的图床），在洛谷内可以使用图床上传图片后复制图片引用地址来使用该图片，具体使用说明可查看操作说明 行内式的图片语法如下： 详细叙述如下：一个惊叹号 !，接着一个方括号，里面放上图片的替代文字（这些文字将在图片加载失败的时候显示），接着一个普通括号，里面放上图片的网址，最后还可以用引号包住并加上选择性的 'title' 文字。 例如： 将会显示图片： logo 自动链接 Markdown 支持以比较简短的自动链接形式来处理网址和电子邮件信箱，只要是用尖括号包起来，Markdown 就会自动把它转成链接。一般网址的链接文字就和链接地址一样，例如： https://www.acgo.cn/ 显示效果为： https://www.acgo.cn/ 分隔线 可以在一行中用三个以上的星号、减号、底线来建立一个分隔线，行内不能有其他内容。也可以在星号或是减号中间插入空格。下面每种写法都可以建立分隔线： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 显示的效果如下： 反斜杠 Markdown 可以利用反斜杠来插入一些在语法中有其它意义的符号，例如：如果你想要用星号加在文字旁边的方式来做出强调效果（但不用 <em> 标签），你可以在星号的前面加上反斜杠。 Markdown 支持以下这些符号前面加上反斜杠来帮助插入普通的符号（加上反斜杠后，这些符号都会以原来的方式显示）： \ 反斜线 ` 反引号 * 星号 _ 底线 {} 花括号 [] 方括号 () 括弧 井字号 * 加号 * 减号 . 英文句点 ! 惊叹号 插入 Bilibili 视频 见 https://www.luogu.com.cn/paste/l9faoe0v。 LaTeX 公式支持 见 LaTeX 说明。

快修!!! 根本过不了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

附魔不要书架吗

自创的？