写这篇博文呢,主要还是为了准备集训队员交流,毕竟分块是我最喜欢的数据结构,所以我就试着写了一篇博文。


基本介绍:

分块是维护较为复杂的信息的,尤其是不满足区间可加性可减性的信息的重要工具。如果运用树状数组或线段树,代码也非常的麻烦和不直观,Debug 可以 Debug 一天。而分块是以一种 “暴力” 的思想来维护信息的,所以非常直观和好理解。其基本思想就是通过把序列划分为多个小块(块长一般为 $\sqrt n$)并预处理出一部分信息保存下来,从而达到维护信息的一种数据结构。分块直观,通用,容易理解和实现。接下来我将以几道例题来谈谈分块。

[Example 1] A Simple Problem with Integers

给定长度为 $N(N\le 10^5)$ 的数列 $A$ , 然后输入 $Q(Q\le 10^5)$ 行指令。

第一类指令形如 C l r d ,表示把数列中第 $l\sim r$ 个数都加 $d$.

第二类指令形如 Q l r ,表示询问数列中第 $l\sim r$ 个数的和.

固然,这道题可以使用树状数组或线段树在 $O((n+m)\log n)$ 的时间复杂度内解决此问题,但是我们现在使用分块来求解。

我们考虑把数列 $A$ 分解成 $N$ 个长度为 $\lfloor \sqrt N\rfloor$ 的段,其中第 $i$ 段左端点为 $(i-1)\lfloor \sqrt N\rfloor + 1$ ,右端点为 $\min(i\lfloor \sqrt N\rfloor,N)$ ,如图所示(大约很丑)。

Blocked

像这样,我们把一个数列分成了 $\sqrt n$ 段。

我们可以预处理出每段的数字之和,存在数组 $sum$ 里面,其中 $sum_i$ 便是第 $i$ 段的区间和,最后另外开一个 $add$ 数组,然后设 $add_i$ 为这个块上还要加的数,起初 $add_i=0$ 。

我们分别进行处理:

  1. 区间加指令。
  • 如果 $l$ 和 $r$ 在同一块 $i$ 里面,暴力修改,把 $A_l,A_{l+1}···A_r$ 都加 $d$ 的同时 $sum_i+=d(r-l+1)$ 。

  • 要不然就让 $l$ 在第 $lb$(Left Block)段,让 $r$ 在第 $rb$(Right Block)段。首先对于 $i \in [lb+1,rb-1]$ ,使 $add_i+=d$ 。然后两端朴素更新。

  1. 区间查询指令。
  • 如果 $l$ 和 $r$ 在同一块 $i$ 里面,暴力查询,答案是 $\sum\limits^{r}_{i=l}a_i+add_i(r-l+1)$ 。

  • 要不然就让 $l$ 在第 $lb$(Left Block)段,让 $r$ 在第 $rb$(Right Block)段。首先对于 $i \in [lb+1,rb-1]$ ,使 $ans+=sum_i+add_i\times len_i$($len_i$ 表示第 $i$ 块的块长)。然后两端朴素查询。

这就是分块算法的基础——对 $add$ 数组的使用。以后可能会用更多的数组来维护一个分块,我们统称其为 “大分块”。不过目前的阶段没有必要碰这个毒瘤的玩意。

因为段数和块长都是 $\sqrt n$ ,所以整个算法的时间复杂度为 $O((n+m)\sqrt n)$ 。

typedef long long ll;
ll a[100010], sum[20010], add[20010];
int L[20010], R[20010];      //左右端点
int pos[100010];             //每个位置属于哪一段
int n, m, t;
void change(int l, int r, long long d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += d;
        sum[p] += d*(r - l + 1);
    }else {
        for (int i = p + 1; i <= q - 1; i++) add[i] += d;
        for (int i = l; i <= R[p]; i++) a[i] += d;
        sum[p] += d*(R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) a[i] += d;
        sum[q] += d*(r - L[q] + 1);
    }
}
ll ask(int l, int r) {
    int p = pos[l], q = pos[r];
    long long ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) ans += a[i];
        ans += add[p] * (r - l + 1);
    }else {
        for (int i = p + 1; i <= q - 1; i++)ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; i++) ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    t = sqrt(n);
    for (int i = 1; i <= t; i++) {
        L[i] = (i - 1)* sqrt(n) + 1;
        R[i] = i* sqrt(n);
    }
    if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
    for (int i = 1; i <= t; i++)for (int j = L[i]; j <= R[i]; j++)pos[j] = i,sum[i] += a[j];
    while (m--) {
        char op[3];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (op[0] == 'C') {
            scanf("%d", &d);
            change(l, r, d);
        }else printf("%lld\n", ask(l, r));
    }
}

呃,这个,大家都知道我是 $\log$ 分块邪教的 (/ω\) 这样的块长是 $\log(n)\times 5$ 最坏时间复杂度是 $O((n+m)\frac{n}{\log n\times5})$ ,在 $Q$ 多的数据下效率非常不错(DarkBZOJ Top1), 但是对于 $n$ 多的数据就会非常坑爹。

请完成例题的代码实现:

请独立思考完成以下习题:


[Example 2] 教主的魔法

给定长度为 $N(N\le 10^6)$ 的数列 $A$ , 然后输入 $Q(Q\le 3\times 10^3)$ 行指令。

第一类指令形如 M l r d ,表示把数列中第 $l\sim r$ 个数都加 $d$.

第二类指令形如 A l r k ,表示在区间 $l\sim r$ 求大于等于 $k$ 的数的个数.

修改操作在前面已经说过了,大区间打标记,小边角暴力改,最后区间要查询的就是 $k-add_i$,修改时直接排序。

我们再来考虑询问操作,直接把查询的块排好序,然后二分查找 $k$ 的值,最后边角料直接暴力检查是不是大于等于 $k$ 。

然后就可以过了。注意单块查询的时候考虑 $add$ 数组的值。

复杂度大约是 $O(n\log n +m\sqrt{n \log n})$。

其实代码实现还是挺简单的。

#define fir(a, b, c) for(register int a = b; a <= c; a ++)
int n, q, a[N], b[N], l[N], r[N], pos[N];
int t, tag[N];
inline int ask(int x, int y, int k){
    int ans = 0;
    if(pos[x] == pos[y]){
        fir(i, x, y)
            if(a[i] + tag[pos[x]] >= k) ans ++;
        return ans;
    }
    fir(i, x, r[pos[x]])
        if(a[i] + tag[pos[x]] >= k) ans ++;
    fir(i, l[pos[y]], y)
        if(a[i] + tag[pos[y]] >= k) ans ++;
    fir(i, pos[x]+1, pos[y]-1){
        int p = lower_bound(b+l[i], b+r[i]+1, k-tag[i])-b;
        ans += r[i]-p+1;
    }
    return ans;
}
inline void change(int x, int y, int k){
    if(pos[x] == pos[y]){
        fir(i, x, y) a[i] += k;
        fir(i, l[pos[x]], r[pos[x]]) b[i] = a[i];
        sort(b+l[pos[x]], b+r[pos[x]]+1);
    }else{
            fir(i, x, r[pos[x]]) a[i] += k;
            fir(i, l[pos[x]], r[pos[x]]) b[i] = a[i];
            sort(b+l[pos[x]], b+r[pos[x]]+1);
            fir(i, l[pos[y]], y) a[i] += k;
            fir(i, l[pos[y]], r[pos[y]]) b[i] = a[i];
            sort(b+l[pos[y]], b+r[pos[y]]+1);
        fir(i, pos[x]+1, pos[y]-1) tag[i] += k;
    }
}
int main(){
    scanf("%d %d", &n, &q);
    fir(i, 1, n) scanf("%d", &a[i]), b[i] = a[i];
    t = sqrt(n);
    fir(i, 1, t) l[i] = (i-1)*t+1, r[i] = i*t;
    if(r[t]<n) t ++, l[t] = r[t-1]+1, r[t] = n;
    t = 1;
    fir(i, 1, n)
        if(i > r[t]) t ++, pos[i] = t;
        else pos[i] = t;
    fir(i, 1, t) sort(b+l[i], b+r[i]+1);
    char opt;int x, y,z;
    while(q --){
        cin>>opt; 
        scanf("%d %d %d", &x, &y, &z);
        if(opt == 'A') printf("%d\n", ask(x, y, z));
        else change(x, y, z);
    }
}

好吧其实要注意的地方还挺多的… 当时是调了一个晚上差不多。

请完成例题的代码实现:

请独立思考完成以下习题:

[Example 3] 蒲公英

给你一个长度为 $n$ 的数列 $a$ ,有 $m$ 次询问,每次询问一个区间 $l\sim r$ ,求该区间的区间众数。如果众数有多个,则输出最小的那一个。注意,你的算法必须是在线的。

考虑 $O(n\sqrt{n\log n})$ 做法:预处理所有以段边界为端点的区间 $[l,r]$ 的众数,再对每个数字建一个 vector 桶,按顺序保存该数值在序列 $a$ 中每次出现的位置。

对于每个询问,扫描 $[l,L)$ ,$(R,r]$ 中每个数 $x$ ,在对应的 vector 里二分查找即可得到答案。

const int maxn=1e5+5;
typedef long long ll;
int size,belong[maxn];
int f[505][505];int cnt[maxn];
vector<int>s[maxn],v;
int n,m;
int val[maxn];
int ans;
int a[maxn];
inline void prework(int x){
    memset(cnt,0,sizeof(cnt));int mx=0,ans=0;
    for(int i=(x-1)*size+1;i<=n;i++){
        cnt[a[i]]++;
        if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&val[a[i]]<val[ans]))ans=a[i],mx=cnt[a[i]];
        f[x][belong[i]]=ans;
    }
}
inline int find(int l,int r,int x){
    return (int)(upper_bound(s[x].begin(),s[x].end(),r)-lower_bound(s[x].begin(),s[x].end(),l));
}
inline int query(int l,int r){
    int ans=f[belong[l]+1][belong[r]-1],mx=find(l,r,ans);
    for(int i=l;i<=min(belong[l]*size,r);i++){
        int t=find(l,r,a[i]);
        if(t>mx||(t==mx&&val[a[i]]<val[ans]))mx=t,ans=a[i];
    }if(belong[l]!=belong[r]){
        for(int i=(belong[r]-1)*size+1;i<=r;i++){
            int t=find(l,r,a[i]); 
            if(t>mx||(t==mx&&val[a[i]]<val[ans]))mx=t,ans=a[i];
        }  
    }return ans;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read();
    m=read();
    v.push_back(-1);
    size=sqrt(n);
    for(int i=1;i<=n;i++)a[i]=read(),v.push_back(a[i]);
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++){
        int b=a[i];
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        val[a[i]]=b;
    }for(int i=1;i<=n;i++)s[a[i]].push_back(i);
    for(int i=1;i<=n;i++)belong[i]=(i-1)/size+1;
    for(int i=1;i<=belong[n];i++)prework(i);
    for(int i=1;i<=m;i++){
        int l,r;l=read();r=read();
        l=(l+ans-1)%n+1;r=(r+ans-1)%n+1;
        if(l>r) swap(l,r);
        print(ans=val[query(l,r)]);
        putchar('\n');
    }
}

感谢 Bovine__Kebi 提供的 $O(n\sqrt{n\log n})$ 代码。

请完成例题的代码实现:

请独立思考完成以下习题:


我们现在分块的学习可以入门了。(也许我可以搞个进阶教程)我们掌握了分块的思想和基本操作,那么非常感谢您能阅读到这里!!!谢谢 qwq

如有谬误,敬请指正 qwq

分类: 文章

Sora1336

Sora。对一切怀着热诚的心。

8 条评论

lhd2006 · 2020年7月19日 6:53 下午

删我账号干嘛

boshi · 2020年7月19日 8:14 上午

推荐 Yuno loves sqrt technology I 和 Yuno loves sqrt technology III

Qiuly · 2020年7月18日 4:12 下午

感谢发文 /qq

    Inversentropir_36 · 2020年7月18日 6:14 下午

    /qq Qiuly

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code