[心之碎片] - 分块初步

柿子饼同学

分块思想很常见, 本期是相对简单的 分块思想 和 分块的数据结构
这几天学的包括 分块决策, 简单莫队, 分块维护什么什么
区间 tag 操作一定要写 pushdown !!!!!
遇到散块就要 pushdown !!! 更换 tag 要注意
下标不要套错了, 不要混淆值和位置之类的
CF444C


分块决策思想 (根号分治)
如果我们发现一个算法的时间复杂度对值域很敏感, 或者这个算法只适用于一部分的值域
就考虑分块决策, 用多种算法分别对应多个值域, 使得复杂度平衡下来
莫队配合值域分块 的目的也是平衡

栗子1 - 青蛙跳
现在有n堆食物，依次编号为1到n，每堆上有Ai的食物
青蛙的弹跳值是t，如果青蛙在x位置上，它起跳后，就会依次去t+x，x+2*t….，一直跳到没有食物为止
嘟想知道，当他把青蛙放在x上，且青蛙的弹跳值为t时，可以获得多少的食物

发现只用枚举 t 的时候, t 很小的情况下会超时, 如果用 dp 做, 空间会超, 而且 t 大的时候有很多不必要计算
所以以 sqrt(n) 为界, t 小的时候用 dp预处理, t 大的时候暴力跳, 这样一次操作的复杂度不会超过 O(sqrt(n))

栗子2 - 微信步数
为了促进懒人国的体育发展，懒人国国王举办了有着丰厚奖品的微信步数竞争大赛。
现在懒人国国王知道懒人国所有国民之间的好友关系。懒人国国王想要知道国民的锻炼情况。
对此，他想要知道对于一个人，他好友里（包括他自己）微信步数最多的是多少。
输入格式
第一行三个整数分别表示总人数，好友关系数量，还有操作数。
然后输入边, 一次操作询问 x 相连的点权值最大值, 一次操作把 x 的权值加上 k

如果一个点连的点很少, 直接暴力即可
如果一个点连的点很多(胖点) , 我们就可以直接先把和这些点相邻的点找出来, 每次更新一个点的时候把(胖点) 顺便更新答案

分块/莫队
分块可以看成不同的视角, 比如维护的时候可以当作线段树类似的方法维护
每个块可以想象成一个普通点, 这样可以在块上搞事情, 比如前缀块众数什么的
每个块可以缩小范围, 比如要跳出序列的路径长度, 可以用分块维护每个点跳出块的长度和跳到哪里, 从而限定范围容易维护修改
分块的应用非常灵活, 这时要注意开阔思路, 例如权值对应下标, 缩小范围方便维护等等
莫队就是简单入个门...
遇到不好维护的东西想想离线 + 莫队

栗子
P1494 [国家集训队] 小 Z 的袜子
珂朵莉树/分块
DZY Loves Colors
注意推加法柿子时用的 N - x 的技巧, 注意除法分类时的分块决策 (小的预处理, 大的暴力算)
P5355 [Ynoi2017] 由乃的玉米田
莫队配合值域分块, 平衡了复杂度, 比树状数组优
P4396 [AHOI2013] 作业
限定范围好维护
P3203 [HNOI2010] 弹飞绵羊
值对应下标
P4137 Rmq Problem / mex

FishC

哎呀，今天我们的主题是“分块思想”，就像把一块大蛋糕切成小块，这样才能方便大家分享和享用！今天我就用一些通俗易懂的例子来带你了解这个有趣的概念。

### 什么是分块思想？
分块思想就像你在健身房里，如果你一次性举起了一吨重的杠铃，那么你的肌肉可能会拒绝合作，甚至可能引发你的肌肉抗议（也就是暴力超时）。此时，你可以选择分几次举，每次举一点，最终完成你的目标。算法中的分块思想同样也是如此，通过把问题分成若干个小块来提高效率。

### 青蛙跳 — 举个栗子
想象一下，有一只青蛙，它正在寻找食物，但是它的食物被放在了n堆上，每堆的食物数量是A[i]。这只青蛙的弹跳值是t。好吧，我们都知道青蛙是懒惰的，所以它决定不一次性检查所有食物，而是采取一种聪明的方式：根据t的大小来选择不同的方法。

- **当t小的时候**：它可以在小范围内使用dp预处理，这样可以快速找到食物。
- **当t大的时候**：那就直接暴力跳吧，反正跳得不远，干脆一步到位。

最终，这种方法可以让青蛙在时间复杂度上不超出O(√n)，就像把一顿大餐分成多道菜，不至于撑坏肚子！

### 微信步数 — 懒人国王的心思
接下来，我们来看一下懒人国。国王关心的是国民们的运动情况。他想知道每个人朋友中的最高步数。这里我们就可以利用分块思想来提高效率。

- **直接暴力法**：对于朋友关系少的人，可以用暴力法，直接挨个查找步数，跟查账一样，容易又粗暴。
- **对于朋友关系多的人**：我们可就要聪明点了，先找出相邻的点，更新的时候顺便更新朋友的步数，这样就能快速得到答案。

### 小总结
分块思想让我们能够智能地选择合适的方法来处理不同规模的问题。想象一下，在生活中，如果你要清理一个房间，完全可以先把玩具、书本、衣物分块整理，再一步步处理，效率会高得多啊！

记住，遇到复杂的问题，不妨试试“分块”，“莫队”，不然你可能会像青蛙一样，一不小心就被“超时”了哦！希望这些幽默而通俗的解释能帮你理解分块思想的魅力！如果还有问题，随时来问我吧！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

简柠啦

1101378861

闪光少年

FishC 发表于 2024-7-22 21:18
哎呀，今天我们的主题是“分块思想”，就像把一块大蛋糕切成小块，这样才能方便大家分享和享用！今天我就用 ...

11

FishC

闪光少年 发表于 2024-07-24 09:33
11

哈哈，看来你是在测试我对数字的接受能力！那么让我用一点幽默来回应：11这个数字就像一个执着的双胞胎，总是想和自己在一起，永远不分开。它在数学中也有很多神奇之处，比如说，它是一个质数，无法被其他比1和11小的正整数整除。

如果你有更具体的问题或者想聊聊关于11的某些特性，随时告诉我哦！不管是数学、编程还是生活中的小事，我都乐意帮忙！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

小肥狼haoran

你是真厉害啊

bowlderq

懂了

尹玄睿

18408238295

很cool的阳

lwh0602