114514

6/25 21：10 发现团队刷新不出来 @AC君

广搜 模板： regenfallen 6

听说发笔记能精华，所以我来了。 写的不好，内容少，请见谅。 由于图挂了，所以在 这里看 吧。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 分块是一种思想，并不是一种数据结构。 分块的思想，就是把数列适当的分成很多块，分别维护每个块内的信息。这虽然是一种很暴力的思想，但是比暴力快特别多。 对于查询，就是处理整块中的信息，然后再暴力枚举处理处理散块中的信息。 对于修改，和查询一样，先修改整块的信息，再暴力枚举修改散块中的信息。 下面是图： 对于整块就是红色，对于散块就是绿色： 分块的时间复杂度取决于块长，就比如我分的块长是 n\sqrt{n}n ，那么对于修改就是 n\sqrt{n}n ，对于查询也是 n\sqrt{n}n 。 块长我一般用 n\sqrt{n}n ，但是根据 OI-wiki 上说的，应该用均值不等式求，但是我不会qwq。 分块的好处是他有时候短，并且比线段树和树状数组能支持的东西强（除了线段树的特色懒标记）。但是就是时间复杂度太高了。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 比如线段树模板题，要求支持区间加与区间和查询，就可以用分块做了。 我们维护这个块内已经堆积的整体加，这个块内所有数的加和，然后再维护每个地方上的数（没有处理块内堆积的加和）。 对于查询，整块的话查红色块内的加和就可以了，散块的话查绿色块内的现在真实的数（数加上块堆积的整体加）。 对于修改，整块直接改标记，让标记加上修改的数，对于散块枚举所有数，让这个数单独加上修改。 我们就愉快的用分块水过线段树啦！ 时间复杂度 O(nn)O(n \sqrt{n})O(nn )，明显劣于线段树的 O(nlog⁡n)O(n \log n)O(nlogn)，但是他码量小。 P3372 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 其实分块还可以是静态的，解决的东西也多了。 如区间众数，可以 这样 处理。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如简介所说的，分块是个 思想，别把它看作数据结构来搞。 弹飞绵羊，正解 LCT，分块是歪解（？） 首先暴力肯定是模拟每个地方往后弹到了哪里然后继续往后弹。 可以先把他分成 n\sqrt{n}n 块，维护每个数弹几次能弹出该块，和弹出该块后会跑到哪里。 先说查询，其实查询就是模拟一下每次跳到哪里了，答案加上跳了几次。 再说修改。显然修改是不会影响到其他块的，所以我们再把块内的东西重搞一遍。 对于构造这两个数组，“弹出该块后会跑到哪里”数组直接算可以吧，“弹几次能弹出该块”这个是可以递推出来的。所以构造这两个数组的时间复杂度是 O(n)O(n)O(n)。 所以总时间复杂度 O(nn)O(n \sqrt{n})O(nn )。 代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 练习： P1975 [国家集训队] 排队。 给你一个数列，要求支持区间加法，区间内小于 xxx 数的个数。 给你一个数列，要求支持单点修改，求区间内第 kkk 大的数是什么。 对于最后一个问题，目前处于口胡状态。现在思路是对于每个块维护一个排好序的数列。对于修改，修改块内哪个数列（插入排序 O(n)O(\sqrt{n})O(n ) 实现）。对于查询，二分答案（区间是值域）然后 check，check 中二分每个块内有多少个小于 mid 的数，然后最后和 kkk 比较（类似 P10417），时间复杂度 O(nlog⁡nlog⁡V)O(\sqrt{n} \log n \log V)O(n lognlogV)。如果不可做就别做了。

众所周知,在第九次排位赛时官方加入了Python提交的功能,ACGO的人数也随之上升,那么接下来我们就来讨论下社区到底有多少人 这是官方发表的帖子,阅读量超过了14w,根据官方设置的,一个人最多给阅读量增加五次这一设定,用144138去 ÷\div ÷ 5 可以得到结果为28827.6,四舍五入保留整数就是28828,所以个人认为社区共有28828人 请各位发表自己的看法,谢谢

ばかやろう！

此团名为"交流天地"，历史悠久，值得信赖 在这个团人人都是管理员！！！ 可以随便交流，没有小黑屋 致力于创造一个自由的"国度" 加入我们

无敌了

66666

带SPJ的 官方的那个没有多个答案 checker代码展示 我都写了官方还不改？？？？？？？

群ID977603428，仅中国团队的可加入，加入后备注ACGO用户名+ID 链接 立即加入中国团队获得进入中国团队官群的资格

只要你有能力，就来吧！

点我去团队 点我去竞赛 邀请码：46PQ

你们不打派系？

老师，我那个代码是对的，可是他输出的和你给我们的那个输出的不一样。

大家喜欢我的🐎🐎头像吗 喜欢的扣1

徐浩东把我们广深一班入侵了徐浩东，你入侵两三个营地就算了，你是什么浑水都要碰一下是吧，我知道你一定看得见，你在4:30加了我，请退出我们班的作业与测试，我不骂你，但你要是得寸进尺的话，那别怪我们的老师不客气