Loading [MathJax]/jax/output/HTML-CSS/jax.js

【算法】浅谈数列分块问题 – Sora1336

于由Sora1336发布

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

基本介绍：

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

[Example 1] A Simple Problem with Integers

给定长度为 N(N≤105) 的数列 A ， 然后输入 Q(Q≤105) 行指令。

第一类指令形如 C l r d ，表示把数列中第 l∼r 个数都加 d.

第二类指令形如 Q l r ，表示询问数列中第 l∼r 个数的和.

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

我们考虑把数列 A 分解成 N 个长度为 ⌊√N⌋ 的段，其中第 i 段左端点为 (i−1)⌊√N⌋+1 ，右端点为 min(i⌊√N⌋,N) ，如图所示（大约很丑）。

Blocked

像这样，我们把一个数列分成了 √n 段。

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

我们分别进行处理：

  1. 区间加指令。
  • 如果 l 和 r 在同一块 i 里面，暴力修改，把 Al,Al+1···Ar 都加 d 的同时 sumi+=d(r−l+1) 。

  • 要不然就让 l 在第 lb（Left Block）段，让 r 在第 rb（Right Block）段。首先对于 i∈[lb+1,rb−1] ，使 addi+=d 。然后两端朴素更新。

  1. 区间查询指令。

  • 如果 l 和 r 在同一块 i 里面，暴力查询，答案是 r∑i=lai+addi(r−l+1) 。

  • 要不然就让 l 在第 lb（Left Block）段，让 r 在第 rb（Right Block）段。首先对于 i∈[lb+1,rb−1] ，使 ans+=sumi+addi×leni（leni 表示第 i 块的块长）。然后两端朴素查询。

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

因为段数和块长都是 √n ，所以整个算法的时间复杂度为 O((n+m)√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));
    }
}
C++
Copy

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

请完成例题的代码实现：

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

[Example 2] 教主的魔法

给定长度为 N(N≤106) 的数列 A ， 然后输入 Q(Q≤3×103) 行指令。

第一类指令形如 M l r d ，表示把数列中第 l∼r 个数都加 d.

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

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

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

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

复杂度大约是 O(nlogn+m√nlogn)。

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

#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);
    }
}
C++
Copy

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

请完成例题的代码实现：

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

[Example 3] 蒲公英

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

考虑 O(n√nlogn) 做法：预处理所有以段边界为端点的区间 [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');
    }
}
C++
Copy

感谢 Bovine__Kebi 提供的 O(n√nlogn) 代码。

请完成例题的代码实现:

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

我们现在分块的学习可以入门了。（也许我可以搞个进阶教程）我们掌握了分块的思想和基本操作，那么非常感谢您能阅读到这里！！！谢谢 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

    回复

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注