当前位置: 首页 > news >正文

根号大杂烩

序列分块

把一个数组简单地划分为若干块,若操作范围覆盖整块则整体操作,反之则暴力操作。由均值不等式可证,块长取 \(\sqrt{n}\) 可得到最优理论复杂度。
由于可以暴力操作且具有简单的结构,它有着比树形数据结构更为灵活的优势。同时,它还具有常数小的优势。

习题

以下是比较板的题:

  • 【模板】线段树 1,跑的比递归式线段树快。

  • 教主的魔法,分块+二分答案,单次查询复杂度 \(O(\sqrt{n}\log n)\)

  • [Ynoi Easy Round 2017] 由乃打扑克,分块+二分答案+二分查找。

以下是比较有挑战的题:

[SNOI2022] 军队

题意简述:区间相同颜色加,区间两种颜色合并,区间求和。
注意到块内的颜色数单调不增。因此我们每个块内维护一个森林,叶子节点即为每个城市,向上代表颜色。接下来详细讲解各种操作:

  • 整块:

    • 颜色加:直接在颜色节点打 \(tag\)
    • 颜色合并:若两种颜色都存在则新建父节点,将两种颜色合并上去,否则直接改颜色。可以证明最多新建 \(2\) 倍叶子节点数量的节点数。
  • 散块:
    全部依靠暴力重构操作。

    • 颜色加:重构期间判断新颜色,直接加。
    • 颜色合并:重构期间记录新颜色,直接合并。

如果重构部分写 pushdown 状物复杂度是线性的,如果从底加到顶要带个 \(\log\)。不过带 \(\log\) 也能过。
可以离线后逐块处理实现线性空间。

[Ynoi2018] 五彩斑斓的世界

突刺贯穿的第二分块。
解法:分块+并查集。开一个值域大小的并查集,这样我们就可以 \(O(1)\) 修改所有块内相同的值。同时通过维护 \(siz\) 数组来快速查询某数出现的次数,且可以随并查集的合并而合并。
接下来进行复杂度分析。注意到,对于本题的修改操作,块内的最大值 \(maxn\) 单调不增。\(maxn\) 最大为 \(10^5+1\)\(m\) 最大为 \(5\times 10^5\),可以视为均摊 \(O(1)\)
对于整块的修改操作,我们分两种情况讨论:
\(2x\ge maxn\) 时,令所有大于 \(x\) 的数减去 \(x\),此时暴力更新 \(maxn\)
\(2x< maxn\) 时,令所有小于等于 \(x\) 的数加上 \(x\),再将块上的 \(tag\)\(x\),表示真实值为整体减 \(tag\)
对于散块,暴力拆散原来的并查集,直接修改并更新 \(maxn\) 就好。
整块更新是均摊 \(O(1)\),散块更新是均摊 \(O(\sqrt n)\)
同上一道题,离线后逐块处理以实现线性空间。
以上方法无法正确处理 \(a_i=0\) 的情况。注意到,修改操作不会产生新的 \(0\),所以直接在一开始用前缀和处理掉 \(0\) 的询问,之后就不用管了。

莫队

很神的技巧。对于一些题目,如果所求的东西难以用常规数据结构维护且可以离线,那就可以尝试莫队。我们可以来看模板题 [国家集训队] 小 Z 的袜子。
考虑维护双指针 \(l,r\) 表示当前考虑区间 \([l,r]\),我们可以容易地从 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 转移过来。那么在移动指针的同时 \(O(1)\) 修改当前的每种颜色袜子数的平方和即可。设当前某颜色的袜子数为 \(x_i\),答案就是

\[\frac{\sum x_i^2+\sum x_i}{(r-l+1)(r-l)} \]

现在考虑优化以减少指针移动次数。将询问离线,并将 \(n\) 分块,以询问左端点所在块编号为第一关键字,右端点为第二关键字升序排序。这样做的时间复杂度是 \(O(n\sqrt{m})\) 的。
时间复杂度证明:
序列长度为 \(n\),询问次数为 \(m\)
首先证明最优块长。设块长为 \(len\),则总块数为 \(\dfrac{n}{len}\),左指针共移动 \(O(m\cdot len)\) 次,右指针共移动 \(O(\dfrac{n^2}{len})\) 次。总共移动 \(m\cdot len+\dfrac{n^2}{len}\) 次。由均值不等式,有

\[m\cdot len+\frac{n^2}{len}\ge 2n\sqrt{m} \]

当且仅当 \(m\cdot len=\dfrac{n^2}{len}\) 时等号成立,此时 \(len=\dfrac{n}{\sqrt{m}}\)
代入,得

\[m\cdot len+\frac{n^2}{len}=2n\sqrt{m} \]

故时间复杂度 \(O(n\sqrt{m})\)


以下是一些莫队技巧

奇偶排序优化

在排序右端点时,若当前左端点块编号为奇数则升序排序,反之则降序排序。

关于指针移动顺序

由于莫队经常要维护桶,在指针移动时若先执行 delete 操作,容易访问桶的负下标造成 RE,所以建议先写 add 操作再写 delete 操作。

莫队+值域分块

值域分块 \(O(1)\) 单点修改的特性很适合莫队的指针移动。
习题:

  • [AHOI2013] 作业

  • 参数要吉祥

莫队+bitset

和值域分块类似,但是更好写一些。
习题:

  • Rmq Problem / mex

  • 小清新人渣的本愿

带修莫队

模板题 [国家集训队] 数颜色 / 维护队列。
现在仅 \(l,r\) 不足以表达当前状态,需要加上时间维度,即 \(l,r,t\)
现在排序以左端点所在块为第一关键字,右端点所在块为第二关键字,时间为第三关键字。设 \(n,m,t\) 同阶,块长设为 \(n^{2/3}\),可得到理论最优时间复杂度 \(O(n^{5/3})\)。详细证明及 \(n,m,t\) 不同阶时的具体分析较为繁琐,可以看 OI Wiki 中的证明。

树上莫队

把树拍到括号序上,记录 \(vis\) 数组表示当前选/不选节点,每次访问到节点时反转 \(vis\) 即可。

http://www.hskmm.com/?act=detail&tid=21667

相关文章:

  • 学习java的第二天
  • 日记.txt
  • Beatty 定理
  • 2025-9-27 提高组模拟赛 div2
  • part2
  • Controversial Rounds
  • 题解:B4410 [GESP202509 一级] 金字塔
  • 9.30总结
  • pytorch基本运算-torch.normal()函数输出多维材料时,如何绘制正态分布函数图
  • AT_agc035_c [AGC035C] Skolem XOR Tree
  • 动手动脑 - A
  • 2025.9.30总结 - A
  • 详细介绍:第14章 AI Agent——构建自主智能助理
  • PowerToys新工具Light Switch:让Windows自动切换明暗主题
  • java从word模板生成.doc和.wps文件
  • 炼石#8 T1
  • 详细介绍:《C++ Primer Plus》读书笔记 第二章 开始学习C++
  • 【虚拟机】“:域名解析出现暂时性错误”VMware配置DNS
  • 双抗 ADC:如何突破传统 ADC 瓶颈,成为癌症治疗的精准杀伤利器?
  • 微信聊天记录移动到外置磁盘后,如何解决无法引导聊天记录
  • AI+手搓第一个AI Agent“AI胜铭兰”
  • 基于JDK17的GC调优策略
  • 【MC】我的世界schematic方块坐标提取转为json
  • Jenkins+IIS+Bonobo.Git.Server 搭建适用dotnet开发者的小团队的devops环境
  • JDK17新特性梳理
  • 完整教程:Nginx 高级配置指南:Rewrite、If判断、浏览器分离与防盗链
  • 数据结构学习随笔 第一章
  • 函数-参数+作用域
  • 用 Nim 实现英文数字验证码识别
  • 抓紧上车,别再错过啦, Github 开源后台管理平台,Naive UI !!!