分块是优雅的暴力——一位$dalao$

hzwer dalao的blog

$Level\ \ 1$

题面

给出一个长为$n$的数列，以及$n$个操作，操作涉及区间加法，单点查值。

数据范围与约定

对于$100$%的数据,$1\le n\le 50000,others/ans\in INT$

题解

作为分块的第一题,它具有最小的难度和最强的代表性.题目要求区间修改单点查询,事实上通过树状数组也是可以完成的.那么接下来我们看看分块怎么做.

分块就像字面意思,把数列分成若干块,使得信息的统计和修改更加容易不必精确到点,节省了时间.分块主要分两种情况讨论:

1. 不完整的块只需要靠暴力来扫即可.
2. 完整的块可以做整体操作来节省时间,这也是分块和暴力相比最优越的地方.

分多少块呢?如果我们每块的大小是$size$,则处理每一整块需要$\Theta(1)$的复杂度,一共有$n/m$块,两边不完整的块最多有$2m$个元素,所以复杂度是$\Theta(n/m)+\Theta(m)$,根据均值不等式,我们可以得出当分$\sqrt{n}$块时复杂度是最小的.可以通过代码来感受一下分块过程:

struct node {
    int tag, l, r;
}part[N];//块结构体
...
int size = sqrt(n)//每块的大小;
part[1].l = 1;
for (int i = 1; i <= n; ++i) {
    bel[i] = cnt;//序列中第i个位置属于第几块
    if (i % size == 0) {//一整块
        part[cnt].r = i;
        part[++cnt].l = i + 1;//增加新的块
    }
}
part[cnt].r = n;

接下来我们回到问题,来分析一下该怎么实现区间修改和单点查询.因为要按块来整体操作,所以我们对每一个块打一个$tag$,表示加法标记.当我们的区间修改覆盖整块的时候,我们直接令这一块的$tag$增加.如果不是一整块就暴力扫描.当我们要单点查询的时候,只需要让数列中的值加上它所属的块的加法标记即可.

read(opt);
if (opt) {
    int x, y, z;
    read(x), read(y), read(z);
    printf("%lld\n", a[y] + part[bel[y]].tag);//输出只需要加上加法标记.
}
else {修改需要判定一些边界,如是不是完整块,左右端点是不是在同一块中.
    int x, y, z;
    read(x), read(y), read(z);
    if (part[bel[x]].l == x && part[bel[y]].r <= y)
        part[bel[x]].tag += z;//如果左端点恰好是一块的起点,区间覆盖一整块就直接加
    else
        for (int i = x; i <= min(part[bel[x]].r, y); ++i)
            a[i] += z;//x,y可能同块,所以要取min
    if (bel[x] == bel[y])
        continue;
    if (part[bel[y]].r == y && part[bel[y]].l <= x)
        part[bel[y]].tag += z;
    else
        for (int i = y; i >= part[bel[y]].l; --i)
            a[i] += z;
    for (int i = bel[x] + 1; i <= bel[y] - 1; ++i)
        part[i].tag += z;//把剩下的块直接处理
}

这样我们就完成了第一个分块题.

$Level\ \ 2$

题面

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。

数据规模与约定

对于$100$%的数据,$1\le n\le 50000,others/ans\in INT$.

题解

这道题就不是用各种数据结构都可以维护的了.我们考虑如何把数列分成一块一块的来分别处理.

首先我们根据分块的原则,如果处理的区间没有覆盖一个完整的块,我们就用暴力来扫描,反正也花不了多少时间.如果覆盖一个完整的块,我们又该怎么处理呢?类似于求区间第k小的操作,我们是通过二分查找来看区间中有多少个数符合要求的.但是二分的前提是区间内的数是单调的.但是又不能直接给原序列排序,怎么办呢?我们可以保存一个原序列的副本,然后分完块后对每一块排序,这样如果不能覆盖完整块,就在原序列上暴力扫,如果覆盖了完整块,就在有序的副本上二分查找得出答案.

询问部分的代码:

if (op) {
    int x, y, z;
    read(x), read(y), read(z), z *= z;
    if (bel[x] == bel[y]) {
        int tot = 0;
        for (int i = x; i <= y; ++i)
            tot += (a[i] + part[bel[x]].tag < z);
        printf("%d\n", tot);
    }
    else {
        int tot = 0;
        if (part[bel[x]].l == x)
            tot += ef_find(part[bel[x]].l, part[bel[x]].r, z) - part[bel[x]].l;
        else {
            for (int i = x; i <= part[bel[x]].r; ++i)
                tot += (a[i] + part[bel[x]].tag < z);
        }
        if (part[bel[y]].r == y)
            tot += ef_find(part[bel[y]].l, part[bel[y]].r, z) - part[bel[y]].l;
        else {
            for (int i = y; i >= part[bel[y]].l; --i)
                tot += (a[i] + part[bel[y]].tag < z);
        }
        for (int i = bel[x] + 1; i <= bel[y] - 1; ++i)
            tot += ef_find(part[i].l, part[i].r, z) - part[i].l;
        printf("%d\n", tot);
    }
}

还有修改呢?参考上一题,我们发现可以维护一个加法标记.但是不完整的块加完之后不一定是递增的,因此要对这一块重新排序来获取单调性.在整个过程中要保持有序副本和原数列的高度同步,不然很容易错.

修改部分的代码:

else {
    int x, y, z;
    read(x), read(y), read(z);
    if (part[bel[x]].l == x && part[bel[x]].r <= y)
        part[bel[x]].tag += z;
    else {
        for (int i = x; i <= min(part[bel[x]].r, y); ++i)
            a[i] += z;
        for (int i = part[bel[x]].l; i <= part[bel[x]].r; ++i)
            sed[i] = a[i];
        sort(sed + part[bel[x]].l, sed + part[bel[x]].r + 1);
    }
    if (bel[x] == bel[y])
        continue;
    if (part[bel[y]].r == y && part[bel[y]].l >= x)
        part[bel[y]].tag += z;
    else {
        for (int i = y; i >= part[bel[y]].l; --i)
            a[i] += z;
        for (int i = part[bel[y]].l; i <= part[bel[y]].r; ++i)
            sed[i] = a[i];
        sort(sed + part[bel[y]].l, sed + part[bel[y]].r + 1);
    }
    for (int i = bel[x] + 1; i <= bel[y] - 1; ++i)
        part[i].tag += z;
}

这就是第二题了.

$Level\ \ 3$

题面

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的前驱（比其小的最大元素）。

数据规模与约定

对于$100$%的数据,$1\le n\le 100000,others,ans\in INT$

题解

其实这个题和上一题基本一样,主要是数据范围方面更加筛掉了暴力.我们只需要稍微改动一下上一题的二分,再改一改对应的操作就可以了.

$Level\ \ 4$

题面

给出一个长为n的数列，以及n个操作，操作涉及区间加法，区间求和。

数据规模与约定

对于$100$%的数据,$1\le n\le 50000,others,ans\in INT$

题解

经典的线段树问题.数据范围比较小,所以我们考虑用分块来做(废话).仍然是区间加法,所以我们还是像往常一样,打好标记.但是这次需要注意的是我们要随时维护区间的和,像线段树那样给每一块打上一个和标记,当需要询问整块信息的时候直接调用即可.否则就暴力处理.需要注意许多初始化,打标记和修改的细节.由于代码冗长且与之前的题目相差无几,我就不再出示代码.

$Level \ \ 5$

题面

给出一个长为n的数列，以及n个操作，操作涉及区间开方，区间求和。

数据规模与约定

对于$100$%的数据,$1\le n\le 50000,others,ans\in INT$

题解

又是一道经典的线段树问题.区间开方是不满足合并的,换句话说,区间中每个数开方不相当于区间和开方.但是我们注意到一个边界性的问题,就是0开方后仍然是0,1开方后还是1.而其他数经过至多5次开方后也会变成1.所以我们在无法整块操作的情况下仍然可以给区间打上一个$times$标记表示这个区间被整体开方过多少次.如果超过4次我们就直接给答案加上$\text{原序列中非0数的个数-原序列中0的个数}$就可以了.其他情况下我们仍然暴力开方.
上代码:

for (int i = 1; i <= n; ++i) {
    int op, x, y, z;
    read(op), read(x), read(y), read(z);
    if (op) {//询问操作
        long long res = 0;
        if (bel[x] == bel[y])
            for (int j = x; j <= y; ++j)
                res += a[j];
        else {
            for (int j = x; j <= part[bel[x]].r; ++j)
                res += a[j];
            for (int j = y; j >= part[bel[y]].l; --j)
                res += a[j];
        }
        for (int j = bel[x] + 1; j <= bel[y] - 1; ++j) {
            if (part[j].times > 4)//times表示被整体开方的次数
                res += part[j].r - part[j].l + 1 - part[j].ze;
            else //ze表示原序列中0的个数
                for (int k = part[j].l; k <= part[j].r; ++k)
                    res += a[k];
        }
        printf("%lld\n", res);
    }
    else {//修改操作
        if (bel[x] == bel[y])
            for (int j = x; j <= y; ++j)
                a[j] = sqrt(a[j]);
        else {
            if (part[bel[x]].l == x) {
                if (part[bel[x]].times <= 4)
                    for (int j = part[bel[x]].l; j <= part[bel[x]].r; ++j)
                        a[j] = sqrt(a[j]);
                part[bel[x]].times++;
            }
            else
                for (int j = x; j <= part[bel[x]].r; ++j)
                    a[j] = sqrt(a[j]);
            /*为了节省篇幅,对y的操作类比省略.*/
        }
        for (int j = bel[x] + 1; j <= bel[y] - 1; ++j) {
            if (part[i].times <= 4)
                for (int k = part[j].l; k <= part[j].r; ++k)
                    a[k] = sqrt(a[k]);
            part[j].times++;
        }
    }
}

$Level\ \ 6$

题面

给出一个长为n的数列，以及n个操作，操作涉及单点插入，单点询问，数据随机生成。

数据规模与约定

对于$100$%的数据,$1\le n\le 100000,others,ans\in INT$

题解

这道题画风突变,出现了一个闻所未闻的”插入”操作.对于数组来说,要插入一个数,就要花费$\Theta(n)$的时间来把后面的元素都往后移一位.而对于链表来说,想要定位一个数则需要$\Theta(n)$的时间.这道题可以使用对二者取长补短的块状链表来实现,不过我不会而且我们的主题是分块,所以我们来想想分块的做法.

由于分块是在数组上实现的,所以插入操作难免会需要暴力.不过普通数组的暴力需要把插入点后面所有的元素都移动,而分块只需要把组内插入点之后的元素移动就可以了.那么我们怎么实现插入呢?暴力是可以的,但我认为更好的选择是使用$STL$的$vector$,这个容器支持$insert$函数,并且能够随时记录自己的$size$.

但是这样有一个问题,如果数据并非随机生成的,而是在一个块内各种插入,那么分块将逐渐退化为普通数组,进而T到飞起.所以我们考虑每$\sqrt{n}$次插入操作就把数列重新分一下块,使得复杂度不会提高很多.(为什么要每$\sqrt{n}$次就重排一次的原因请参考hzwer dalao的blog)并且重排之前别忘了把现在每一块中的$vector$内容赋值到原数组中.
代码:

#include<bits/stdc++.h>
#define N 200005//由于插入操作别忘了数组开大一点
using namespace std;
/*篇幅原因,快读省略*/
int n, a[N], cnt = 1;

struct node {
    int l, r;
    vector<int> c;//每个块的动态数组
}part[2000];

inline void reset() {//重分块函数
    int size = sqrt(n);
    part[1].l = 1, cnt = 1;
    for (int i = 1; i <= n; ++i) {
        part[cnt].c.push_back(a[i]);
        if (i % size == 0) {
            part[cnt].r = i;
            part[++cnt].l = i + 1;
        }
    }
    part[cnt].r = n;
    return;
}

inline void react() {//别忘了先把原数组更新为现在的样子.
    n = 0;
    for (int i = 1; i <= cnt; ++i) {
        if (part[i].c.empty())
            continue;
        for (int j = 0; j < part[i].c.size(); ++j)
            a[++n] = part[i].c[j];
        part[i].c.clear();
    }
    reset();//现在可以重分块了
    return;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    reset();//先分块
    int temp = n, tot = 0;
    while (temp--) {
        int op, x, y, z;
        read(op), read(x), read(y), read(z);
        if (op) {
            int i;
            for (i = 1; i <= cnt; ++i)//查询过程,先定位块
                if (y > part[i].c.size())
                    y -= part[i].c.size();
                else break;//定位完后剩下的就是块内的编号了.
            printf("%d\n", part[i].c[y - 1]);
        }
        else {
            tot++;//记录次数
            for (int i = 1; i <= cnt; ++i)
                if (x > part[i].c.size())
                    x -= part[i].c.size();
                else {
                    part[i].c.insert(part[i].c.begin() + x - 1, y);//插入
                    if (tot > sqrt(n))//如果插入次数多了就重分块
                        react(), tot = 0;
                    break;
                }
        }
    }
    return 0;
} 

$Level\ \ 7$

题面

给出一个长为n的数列，以及n个操作，操作涉及区间乘法，区间加法，单点询问。

数据规模与约定

对于$100$%的数据,$1\le n\le 100000,others,ans\in INT$

题解

这道题的画风逐渐正常,又是一道经典的线段树问题.线段树在维护这两种操作的时候,打了两种标记,所以分块也打了两种标记.但是这两种标记显然是有区别的.因为乘法运算的优先级高于加法.那么我们怎么来维护呢?假设现在一块上先乘后加,得到一个加法标记和一个乘法标记.那么我们考虑如果现在进行整块的加,会发生什么呢?显然,只有加法标记会增加,而影响不到乘法标记.那如果进行乘法呢?乘法和加法标记都需要乘上这个数.所以我们按照这个优先顺序进行整块的操作,非整块的时候我们只能通过把这一块重构暴力来做.
块内重构:

inline void rebuild(int x) {
    for (int i = part[x].l; i <= part[x].r; ++i)
        a[i] = (a[i] * part[x].tagm + part[x].taga) % mod;
    part[x].taga = 0, part[x].tagm = 1;
    return;
}

其他代码和之前的类似.

$Level\ \ 8$

题面

给出一个长为n的数列，以及n个操作，操作涉及区间询问等于一个数c的元素，并将这个区间的所有元素改为c。

数据规模与约定

对于$100$%的数据,$1\le n\le 100000,others,ans\in INT$

题解

到了这个题我才知道,原来块内重构是非常常见的,是我之前把它的复杂度想得太高,结果代码冗长时间也没有节省很多.这个题的询问非常奇怪,又是一个线段树维护不了的题目.分块源于暴力而高于暴力,所以它问什么我们打什么标记.我们给每个块打一个”块内元素是否全部相等,如果相等的话,等于什么”的标记.这个标记听起来很玄学,实际上,当块内标记都相等时,这个标记就赋值为块内的值,否则就赋值为$-inf$.这样我们每当遇到一个区间内有不同元素的块的时候,都要用暴力来统计.这看起来会T(实际上像我一样写丑了也会T),实际上每一块这一次扫完之后,就被赋值成一样的了.下次整块操作的时候就可以直接$\Theta(1)$统计答案了.所以总的复杂度是可以接受的.

$Level\ \ 9$

题面

给出一个长为n的数列，以及n个操作，操作涉及询问区间的最小众数。

数据规模与约定

对于$100$%的数据,$1\le n\le 100000,others,ans\in INT$

题解

来到了$BOSS$关.区间众数是一道经典难题.有的许多方法.这里讲一种基于分块的在线做法.

分块的难点在于它不具有区间可加性.也就是知道两块的众数并不能直接得出这两块整体的众数.但是判断众数的本质是一个数出现的次数,这是满足区间可加性的.我们考虑从这方面来下手.对于分块,我们一贯的思路是整块统计,两端暴力.这一道题也不例外.我们的众数要么是在整块统计中得出的,要么是在两端的暴力过程中得出的.所以对于整块,我们直接统计众数,然后暴力扫描两端看能不能取代已经得到的答案.

现在问题来了,怎么统计若干块之间的众数呢?如果要快速得出,我们肯定不能现问现扫,而是要预处理出来再做.因为区间长度是任意的,我们也应当处理出连续多块之间的众数.前面说了众数的本质是出现次数.我们设t[i][j]表示i在前j块中的出现次数.为了方便统计我们要先离散化以下,让i表示第i小的数.然后固定一个最右边的块,向左扫描到整个序列的左端,中途维护众数,这里出示代码来加强理解:

for (int i = 1; i <= bel[n]; ++i) {//most[i][j]表示第i块到第j块的最小众数.
    for (int j = rt[i]; j; --j) {//t[i][j]表示i在前j块中出现的次数,类似于前缀和
        if (bel[j] != bel[j + 1])//区间分界线先继承一下,方便对比
            most[bel[j]][i] = most[bel[j] + 1][i];
        t[lsh[j].rk][i]++;//出现次数+1
        int nowtemp = t[lsh[j].rk][i], nowans = t[most[bel[j]][i]][i];//检验是否能够取代
        if (nowtemp > nowans || (nowtemp == nowans && lsh[j].rk < most[bel[j]][i]))
            most[bel[j]][i] = lsh[j].rk;//次数多或者次数相等值小就可以取代.
    }
}

现在我们已经知道如何预处理众数了.做法比较暴力.接下来我们就考虑询问.实际上过程是完全类似的.这里直接上代码,并不难理解.

//ap[i]表示i出现的次数,是一个暂存数组
int x, y, ans;
read(x), read(y), ans = most[bel[x] + 1][bel[y] - 1];
if (bel[x] == bel[y]) {
    for (int i = x; i <= y; ++i) {
        ++ap[lsh[i].rk];
        int nowtemp = ap[lsh[i].rk], nowans = ap[ans];
        if (nowtemp > nowans || (nowtemp == nowans && lsh[i].rk < ans))
            ans = lsh[i].rk;
    }
    printf("%d\n", ans = rev[ans]);//别忘了ans其实是一个离散化后的排名
}
else {
//这里通过t数组后减去前来实现中间完整块内出现次数的统计,因为次数满足可加性
    for (int i = x; i <= rt[bel[x]]; ++i) {
        ++ap[lsh[i].rk];
        int nowtemp = ap[lsh[i].rk] + t[lsh[i].rk][bel[y] - 1] - t[lsh[i].rk][bel[x]];
        int nowans = ap[ans] + t[ans][bel[y] - 1] - t[ans][bel[x]];
        if (nowtemp > nowans || (nowtemp == nowans && lsh[i].rk < ans))
            ans = lsh[i].rk;
    }
    for (int i = lt[bel[y]]; i <= y; ++i) {
        ++ap[lsh[i].rk];
        int nowtemp = ap[lsh[i].rk] + t[lsh[i].rk][bel[y] - 1] - t[lsh[i].rk][bel[x]];
        int nowans = ap[ans] + t[ans][bel[y] - 1] - t[ans][bel[x]];
        if (nowtemp > nowans || (nowtemp == nowans && lsh[i].rk < ans))
            ans = lsh[i].rk;
    }
    printf("%d\n", ans = rev[ans]);
}
for (int i = x; i <= rt[bel[x]]; ++i)
    ap[lsh[i].rk] = 0;//清空暂存器
for (int i = lt[bel[y]]; i <= y; ++i)
    ap[lsh[i].rk] = 0;

这就是经典的区间众数问题了.到此我们已经完成了所有的分块入门模板题,体会到分块的原则就是整块统计,两端暴力.通过打标记和块内重构的方法,在保证正确性地情况下来尽量方便省时地实现目的.其时间复杂度往往劣于线段树等高级数据结构,但是其灵活性并不差,并且非常直观.

感谢@suwakow给予的帮助和参考

$\textit{Fin}$