数列分块入门 1

_Fireflies_ · 2025-09-10 20:36:54 · 题解

题目传送门

算法介绍：

分块是一种暴力优雅的数据结构。

分块，顾名思义，在处理一个长度为 n 的序列时，将其分成 k 块，每块内有 t 个元素，需要满足 k \times t \ge n，一般取 k=t= \lceil \sqrt{n} \rceil，在处理一整个块内的元素时 O(1) 打标记，处理剩下的零散元素时暴力修改，因为整块最多只有 \sqrt{n} 个所以对整块的处理复杂度 O(\sqrt{n})，而零散元素最多只有 (2 \sqrt{n} -2) 个，所以对零散元素的处理复杂度也为 O(\sqrt{n})，q 次操作下总复杂度即为 O(q \sqrt{n})。

思路：

显然本题就是分块模板，加法对整块打标记，对零散部分暴力处理即可，复杂度 O(\sqrt{n})，单点查询显然可以做到 O(1)。

代码：

注意 long long。

#include <bits/stdc++.h>
using namespace std;
inline long long read()
{
    long long 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*10+ch-48;ch=getchar();}
    return x*f;
}
long long n;
long long op,l,r,c;
struct node{
    long long l,r;
    long long add;
    long long m[605];
}k[605];
long long B=600;
long long a[300005];
long long mq=0,ms=0;
int main(){
    n=read();
    for(long long i=1;i<=n;i++){
        a[i]=read();
    }
    k[0].l=1;
    k[0].r=B;
    k[0].add=0;
    for(long long i=1;i<=300000;i++){
        ms++;
        if(ms==B+1){
            mq++;
            ms=1;
            k[mq].l=(mq*B)+1;
            k[mq].r=(mq+1)*B; 
            k[mq].add=0;
        }
        if(i>n) k[mq].m[ms]=0;
        else k[mq].m[ms]=a[(mq*B)+ms];
    }
    for(long long i=1;i<=n;i++){
        op=read();
        l=read();
        r=read();
        c=read();
        if(op==0){
            for(long long j=0;j<=mq;j++){
                if(l<=k[j].l&&r>=k[j].r) k[j].add+=c;
                else if(k[j].r<l||k[j].l>r) continue;
                else{
                    for(long long o=1;o<=B;o++){
                        if(l<=(j*B)+o&&r>=(j*B)+o){
                            k[j].m[o]+=c;
                        }
                    }
                } 
            }
        }
        else{
            if(r%B==0) cout<<(k[(r/B)-1].m[B]+k[(r/B)-1].add);
            else cout<<(k[r/B].m[r%B]+k[r/B].add);
            cout<<endl;
        }
    }
    return 0; 
}

572ms，人傻常数大。