题解：P13976 数列分块入门 1

CSPAK_Zhangxiuqi0011 · 2025-09-07 00:44:37 · 题解

前言

非常好的分块入门题，用其他算法的解法也很多。

思路

思路 1：分块

本篇题解重点讲述的内容。
首先，我们要明白，分块的概念。这里我们从纯暴力做法讲起。
如果是纯暴力做法的话，那么对于每次修改操作，就是枚举每个 i(l\le i \le r)，然后暴力对每个数修改，很明显会 TLE。
那么，我们有没有什么办法，优化这个暴力呢？其实是有的，这就是分块。
分块，就是把这个数列分成 \left\lfloor\sqrt n\right\rfloor 或 \left\lfloor\sqrt n\right\rfloor+1 块，每块长度都是 \left\lfloor\sqrt n\right\rfloor。如果 n 是完全平方数，那么就会分成 \left\lfloor\sqrt n\right\rfloor 块，否则在最后会多出来一块小块，称为“角块”。
这样分块之后，进行修改操作的时候，每当修改区间跨越了一个完整的块时，我们就直接把这个块的权值进行修改操作，而不是对这个块内的每个数暴力去修改。而对于修改区间两端的非完整块部分，就直接暴力修改即可。
举个例子：例如数列长度为 11，我们要修改的区间为 [2,10]。
如图，对于第二个块和第三个块，由于这两个整块都在修改区间内，所以我们直接选择把这个块的权值修改。对于第一个和第四个块，我们只能进行暴力修改。以第一个块举例，具体方法是暴力修改从起点开始，到起点所在块结束的部分。第四个块同理。
图中要修改的部分用红色标记出，可供参考。

那么问题来了：如何找到起点和终点（其实就是找到某个位置）在哪个块？
我们假设这个位置是 x，那么找规律可以发现，这个位置所在块编号就是 (x-1)\div\left\lfloor\sqrt n\right\rfloor +1。
那么查询就很容易了吧。本题是单点查询，那么就找到这个点在哪个块，然后答案就是原数组中这个点的权值加上这个点所在块的权值的和。如果是区间查询的话，那么可以按照和上面修改操作差不多的方式做。详细可以看数列分块入门 4。
需要注意的是，修改部分有一个小细节。有可能起点和终点在同一个块内，这时我们应该直接进行暴力修改，否则按照上面的修改方式会 WA。
单次修改时间复杂度：O(\sqrt n)。总时间复杂度 O(n\sqrt n)，可以通过本题。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[300005],num[555];//num[i]：第i个块的权值 
signed main() {
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    int len;
    len = sqrt(n);//每个块的长度
    for(int i = 1;i<=n;i++){
        int op,l,r,c;
        cin>>op>>l>>r>>c;
        if(!op){
            int nl,nr;//起点和终点所在块 
            nl = (l-1)/len+1;
            nr = (r-1)/len+1;
            if(nl == nr){//细节：如果起点和终点在一个块，那么直接暴力修改 
                for(int j = l;j<=r;j++){
                    a[j] = a[j]+c; 
                }
            }else{
                for(int j = l;j<=nl*len;j++){//暴力修改起点到起点所在块的末尾部分 
                    a[j] = a[j]+c;
                }
                for(int j = nl+1;j<nr;j++){//修改中间完整块的部分 
                    num[j] = num[j]+c;
                }
                for(int j = (nr-1)*len+1;j<=r;j++){//暴力修改终点所在块的开头到终点的部分 
                    a[j] = a[j]+c;
                }
            }
        }else{
            int nx;
            nx = (r-1)/len+1;
            cout<<a[r]+num[nx]<<"\n";
        }
    }
    return 0;
}

思路 2：树状数组

其实不难发现这道题就是树状数组的板子，由于树状数组不是本篇题解的重点内容，所以不讲了，可以去自行学习。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[300005],tr[300005],n;
int lowbit(int now){
    return now&(-now);
}
void update(int w,int num){
    for(int i = w;i<=n;i = i+lowbit(i)){
        tr[i] = tr[i]+num;
    }
}
int find(int w){
    int ans;
    ans = 0;
    for(int i = w;i;i = i-lowbit(i)){
        ans = ans+tr[i];
    }
    return ans;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        update(i,a[i]-a[i-1]);
    }
    for(int i = 1;i<=n;i++){
        int op,x,y,k;
        cin>>op>>x>>y>>k;
        if(!op){
            update(x,k);
            update(y+1,-k);
        }else{
            cout<<find(y)<<"\n";
        }
    }
    return 0;
}

思路 3：线段树

其实和树状数组是一个道理，是一个区间修改单点查询的线段树，也不是本题重点，所以也不详细讲述。不会线段树的可以去自行学习线段树。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int l,r,num,len,tag;
}a[1200005];
int b[300005],n;
void pushup(int now){
    a[now].num = a[now*2].num+a[now*2+1].num;
} 
void build(int now,int l,int r){
    a[now].l = l;
    a[now].r = r;
    a[now].len = r-l+1;
    if(l == r){
        a[now].num = b[l];
        return;
    }
    int mid;
    mid = (l+r)/2;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}
void pushdown(int now){
    a[now*2].tag = a[now*2].tag+a[now].tag;
    a[now*2].num = a[now*2].num+a[now*2].len*a[now].tag;
    a[now*2+1].tag = a[now*2+1].tag+a[now].tag;
    a[now*2+1].num = a[now*2+1].num+a[now*2+1].len*a[now].tag;
    a[now].tag = 0;
}
void update(int now,int l,int r,int cg){
    if(a[now].l>r || a[now].r<l){
        return;
    }
    if(l<=a[now].l && a[now].r<=r){
        a[now].num = a[now].num+a[now].len*cg;
        a[now].tag = a[now].tag+cg;
        return;
    }
    pushdown(now);
    update(now*2,l,r,cg);
    update(now*2+1,l,r,cg);
    pushup(now);
}
int find(int now,int w){
    if(a[now].l>w || a[now].r<w){
        return 0;
    }
    if(a[now].l == a[now].r){
        return a[now].num;
    }
    pushdown(now);
    int ans;
    ans = find(now*2,w)+find(now*2+1,w);
    pushup(now);
    return ans; 
}
signed main() {
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>b[i];
    }
    build(1,1,n);
    for(int i = 1;i<=n;i++){
        int op,l,r,k;
        cin>>op>>l>>r>>k;
        if(!op){
            update(1,l,r,k);
        }else{
            cout<<find(1,r)<<"\n";
        }
    }
    return 0;
}