历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

分块算法

作者：

xiehy , 2025-04-15 10:28:24 · 湖北 , 所有人可见 , 阅读 3

优质膜拜大佬

本质：

以下几点虽然是考研内容，但是笔者依然认为具有启发意义，~在这一点上不做争辩~

绪论

数据项是最基本的单位，不可分割
数据元素通常是若干个数据项的组合
数据结构通常包括二要素（这里删掉了物理结构）：逻辑结构（即数据元素之间的逻辑关系，如树形结构，线性结构，集合结构，包含关系，依赖关系）、运算逻辑（比如数据元素维护的东西是如何运算得到的）

算法实例

线段树

实际上说线段树基于分治是很不准确的，只是有点“神韵”在里面，所有的数据结构大概都可以归结到信息的合并。
比如ordinary segment tree就是对于数据的彻底合并，~~有点二分的意思在里面，这个只是合并的规则~~。而persistent segment tree也可以看成对信息的合并，只不过有些节点是空的，但是对于满足合并规则的数据会考虑合并，权值线段树同理。

平衡树

而平衡树可以分为两种，对于维护权值的平衡树是一种树形结构，基于二叉搜索树实现的，只是多了个保证树高的操作，有点二分的感觉，但同时还支持修改的复杂操作。
对于维护序列的平衡树，在这里我最想说的就是它的合并信息的逻辑，在这里将一个元素作为“基”，将这个基左侧的元素放到左边，右边同理，也正是因为这个合并规则它更加的灵活，可以维护一个动态的序列，线段树的划分规则很“死”，仅仅将[l][r]范围内的数据项合并成一个数据元素，一旦数列结构变了，元素下标都会随之改变，那你就要重构了hhh

二者和分块对比

为什么有分块能做的题上述的算法却做不了（比如区间众数,无修改;区间加，查询区间大于等于 k 的数的个数)

从逻辑结构的角度分析，二者都是树形结构，数据元素之间存在依赖关系，在修改的过程中想要维持某一个数据元素的正确性，需要修改树上的一条链。
合并过于完全，而分治是不完全的合并。

题目：

1.P4168 [Violet] 蒲公英

闲话

~~评级：困难~~
记块长为T，数列长度为n，块数为 $\frac{n}{T}$ ,询问数为m
本题中预处理是个大粪（有价值）（这是在笔者还没完全搞懂的时候写的，可以算是思考过程，当然是看了题解的hhh）

思考过程

线段树，主席树很显然不行，因为二者没有可加性，区间众数实在是不像区间和那样具有可加性。
考虑暴力，n*n的时间复杂度显然是接受不了的，考虑暴力优化一下，最常见的就是分块加速（为什么能够加速呢，还是因为上面提到的思想大段维护，因此可以更快）。
不过区间众数在暴力中还是用前缀和性质的桶去暴力扫描的，在分块中我们的目标就是优化时间，对于整块在 $O(1)$ 或者 $O(\log n)$ 或者 $O( \sqrt n )$ 的时间里是可接受的，而这里显然是要预处理的
$ps$ : 如果有修改咋办呢？？？，快帮我想想
对于散点可以直接加入到大段中的桶中，但是这样好像又要重新扫一遍，其实不用，如果我们提前知道大段中的众数，那么新的众数只有可能是原来的众数或散点中的数，因而只用比较块长的数了
现在的问题便成如何高效的找到每一个块区间的
$cnt[id][x]$ （表示在前id块中x的出现次数，当然了要离散化），这个可以在 $O(n \sqrt n)$ 的时间复杂度内完成
对于每一子段块内的众数，暴力扫描是 $O(n^2)$ ，不过这里是预处理，在预处理里面，优化时间常见的就是首先看公式，观察瓶颈在哪里，哪些是可以预处理的，可以新开一些变量来辅助，其次就是尽可能得利用上之前已经的到信息，这一点在KMP预处理中可以体现出来，考虑固定左端点，右端点不断延展，每次延展 $O(\sqrt n)$ ,总体就是 $O(n \sqrt n)$
对于时间复杂度的分析： $O(nT+ \frac{n^2}{T})$ ，当且仅当T取 $n^{\frac{1}{2}}$ 时最优秀

个人错误

对于小于等于两段的询问，应该是直接从l枚举到r。但是我却写成了从l到所在区间的右端点。从r所在区间的左端点到r。对于两段是正确的，但是对于一段会出锅 ~~www~~


    int idl=bel[l],idr=bel[r];
    int ans=0;
    if(idl==idr){//我tm直接暴力
        for(int i=l;i<=r;i++)t[a[i]]++;
//      for(int i=b[idr].l;i<=r;i++)t[a[i]]++;
        int pm=0;
        for(int i=l;i<=r;i++){
            if(t[a[i]]>t[pm]||((t[a[i]]==t[pm])&&a[i]<pm)){
                pm=a[i];
            }
        }
        ans=pm;ans=c[pm];
        lastans=ans;
        printf("%d\n",lastans);
        for(int i=l;i<=r;i++)t[a[i]]--;
//      for(int i=b[idr].l;i<=r;i++)t[a[i]]--;