logo AlgoBeat OnlineJudge
登录 注册
专栏
数列分块

数列分块

_ZXY_
2026-05-16 19:49:26 87 0

我热爱暴力数据结构！
分块是一种暴力的思想，并非算法。

例题 luogu P13976

给出一个长为 的数列。
有 个询问，每行输入四个数字 、、、，以空格隔开。 若 ，表示将位于 的之间的数字都加 。
若 ，表示询问 的值（ 和 忽略）。
保证 。。每次操作后的 满足 。
考虑暴力。
我们可以按题目说的模拟，每次遍历 加， 就输出 ，复杂度 ，明显无法通过。

考虑复杂度正确的做法。
我们可以将数组分成一段一段的“块”。
就像这样：
对于每一个块，我们可以去维护它块内元素的和。在求区间加的时候，对于“不完整”的块直接暴力加，中间的“完整块”打上一个懒标记。这样在求 的值的时候，只需要用 加上 所在块的懒标记了。

时间复杂度 。

这个思想听上去不错，但仍然有一些小细节。

如何计算下标对应的块编号？
我们设预定块长为 ，则编号为 。是什么意思呢？我们先将下标转换为 开头的，这样 就是从 开始的块编号，加一就是 开头的了。

如果 不是 的倍数怎么办？
其实最后一个块不一定是完整的，不影响计算。

块长怎么确定？
块长最好是 。
不难发现上述操作区间修改的时间复杂度是 的。
由二元均值不等式，对 有： 令 ，代入得： 等号成立条件： 所以最优块长为 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+7;
int a[N],b[N],id[N],n,len,s[N];
void add(int l,int r,int x){
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)a[i]+=x,s[id[l]]+=x;//同一块暴力加
        return;
    }
    for(int i=l;id[i]==id[l];i++)a[i]+=x,s[id[l]]+=x;//左边“不完整块”暴力加
    for(int i=id[l]+1;i<id[r];i++)b[i]+=x,s[i]+=len*x;//中间大块打懒标记，更新块内元素和
    for(int i=r;id[i]==id[r];i--)a[i]+=x,s[id[r]]+=x;//右边“不完整块”暴力加
}
signed main(){
    cin>>n;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
        s[id[i]]+=a[i];
    }
    for(int i=1;i<=n;i++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0)add(l,r,c);
        else print("{}\n",a[r]+b[id[r]]);//求值
    }
}

例题 luogu P13982

有 行询问，每行输入四个数字 、、、，以空格隔开。
若 ，表示将位于 的之间的数字都加 。
若 ，表示将位于 的之间的数字都乘 。
若 ，表示询问 的值 （ 和 忽略）。要输出非负的余数值。
考虑如何处理区间乘。

某些群众：我们可以再打个懒标记 呀！

那如何处理区间求和呢？

在打乘法懒标记的时候，我们可以将原来的 懒标记同时乘上 。操作这段区间时下放一下就行了。

如何下放呢？
下放时我们优先下放 ，然后再下放 。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+7,mod=10007;
#define int long long 
int a[N],id[N],mul[N],add[N],n,len;
void reset(int bid){//下放懒标记
    for(int i=(bid-1)*len+1;i<=min(bid*len,n);i++){
        a[i]=((1ll*a[i]*mul[bid])%mod+add[bid]+mod)%mod;
    }//先下放乘，然后加
    add[bid]=0;
    mul[bid]=1;
}
void Add(int opt,int l,int r,int c){
    c%=mod;
    if(id[l]==id[r]){
        reset(id[l]);
        for(int i=l;i<=r;i++){
            if(!opt)a[i]=((a[i]+c)%mod+mod)%mod;
            else a[i]=((1ll*a[i]*c%mod)+mod)%mod;
        }
        return;
    }
    reset(id[l]);
    reset(id[r]);
    for(int i=l;id[l]==id[i];i++){
        if(!opt)a[i]=((a[i]+c)%mod+mod)%mod;
        else a[i]=((1ll*a[i]*c%mod)+mod)%mod;
    }
    for(int i=id[l]+1;i<id[r];i++){
        if(!opt)add[i]=(add[i]+c)%mod;
        else mul[i]=mul[i]*1ll*c%mod,add[i]=add[i]*1ll*c%mod;
    }//add一起乘
    for(int i=r;id[i]==id[r];i--){
        if(!opt)a[i]=((a[i]+c)%mod+mod)%mod;
        else a[i]=((1ll*a[i]*c%mod)+mod)%mod;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=mod;
        id[i]=(i-1)/len+1;
    }
    for(int i=1;i<=n;i++)mul[i]=1;
    for(int i=1;i<=n;i++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt<2)Add(opt,l,r,c);
        else{
            cout<<((a[r]*mul[id[r]]%mod+ add[id[r]])%mod+mod)%mod<<'\n';
        }
    }
}

例题 luogu P13980

第二行输入 个数字，第 个数字为 ，以空格隔开。
有 行询问，每行输入三个数字 ，以空格隔开。
若 ，表示将位于 的之间的数字都开方。对于区间中每个
若 ，表示询问位于 的所有数字的和。
区间开方，发现不能打懒标记。
打我们发现一个性质：一个大数，开 次方，最后也会变成 或 。

所以，开方暴力遍历即可。若该块内元素均已变为 或 ，就跳过这个块。
注意同时维护每个块的和。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+7;
int a[N],b[N],id[N],n,len,s[N];
bool flg[N];
void upd(int j){
    s[id[j]]-=a[j];
    a[j]=(int)sqrt(a[j]);
    s[id[j]]+=a[j];
}
bool check(int bid){
    bool f=1;
    int lf=(bid-1)*len+1,ri=min(n,bid*len);
    for(int i=lf;i<=ri;i++)if(a[i]>1)f=0;
    return f;
}
void sqrted(int l,int r){
    if(id[l]==id[r]){
        if(flg[id[l]])return;
        for(int i=l;i<=r;i++)upd(i);
        flg[id[l]]=check(id[l]);
        return;
    }
    if(!flg[id[l]]){
        for(int i=l;id[i]==id[l];i++)upd(i);
        flg[id[l]]=check(id[l]);
    }
    for(int i=id[l]+1;i<id[r];i++){
        if(!flg[i]){
            int lf=(i-1)*len+1,ri=min(n,len*i);
            for(int j=lf;j<=ri;j++)upd(j);
            flg[i]=check(i);
        }
    }
    if(!flg[id[r]]){
        for(int i=r;id[i]==id[r];i--)upd(i);
        flg[id[r]]=check(id[r]);
    }
}
int query(int l,int r){
    int ans=0;
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)ans+=a[i]+b[id[l]];
        return ans;
    }
    for(int i=l;id[i]==id[l];i++)ans+=a[i]+b[id[l]];
    for(int i=id[l]+1;i<id[r];i++)ans+=s[i];
    for(int i=r;id[i]==id[r];i--)ans+=a[i]+b[id[r]];
    return ans;
}
signed main(){
    cin>>n;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
        s[id[i]]+=a[i];
    }
    for(int i=1;i<=n;i++){
        int opt,l,r,c;
        cin>>opt>>l>>r;
        if(opt==0)sqrted(l,r);
        else print("{}\n",query(l,r));
    }
}

例题 luogu P1471

两个正整数 ，分别表示数列中实数的个数和操作的个数。
第二行包含 个实数，其中第 个实数表示数列的第 项。
接下来 行，每行为一条操作，格式为以下三种之一：
操作 ：1 x y k ，表示将第 到第 项每项加上 ， 为一实数。
操作 ：2 x y ，表示求出第 到第 项这一子数列的平均数。
操作 ：3 x y ，表示求出第 到第 项这一子数列的方差。
首先，我们根据 ，得到

继续推

因为 ，所以上面的式子等于
整理得

所以我们维护一个块内平方和还有块内和就好了。

那如何更新块内平方和呢？
我们发现

等价于

也就是

这一坨其实就是维护的两个和了。

至此，本题解决。

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e5+7;
db a[N],b[N],s[N],s_2[N];
int id[N],len,n,m;
void add(int l,int r,db x){
    int L=id[l],R=id[r];
    if(L==R){
        for(int i=l;i<=r;i++){
            s_2[L]-=a[i]*a[i];
            a[i]+=x;
            s[L]+=x;
            s_2[L]+=a[i]*a[i];
        }
        return;
    }
    for(int i=l;id[i]==L;i++){
        s_2[L]-=a[i]*a[i];
        a[i]+=x;
        s[L]+=x;
        s_2[L]+=a[i]*a[i];
    }
    for(int i=L+1;i<R;i++)b[i]+=x;
    for(int i=r;id[i]==R;i--){
        s_2[R]-=a[i]*a[i];
        a[i]+=x;
        s[R]+=x;
        s_2[R]+=a[i]*a[i];
    }
}
db query1(int l,int r){
    int L=id[l],R=id[r];
    db sum=0;
    if(L==R){
        for(int i=l;i<=r;i++)sum+=a[i]+b[L];
        return sum/(r-l+1);
    }
    for(int i=l;id[i]==L;i++)sum+=a[i]+b[L];
    for(int i=L+1;i<R;i++)sum+=s[i]+b[i]*len;
    for(int i=r;id[i]==R;i--)sum+=a[i]+b[R];
    return sum/(r-l+1);
}
db query2(int l,int r){
    int len=r-l+1,pl=id[l],pr=id[r];double ave=0,ans=0;
    if(pl==pr){
        for(int i=l;i<=r;i++)ave+=a[i]+b[pl],ans+=(a[i]+b[pl])*(a[i]+b[pl]);
        return ans/len-(ave/len)*(ave/len);
    }
    for(int i=l;id[i]==pl;i++)ave+=a[i]+b[pl],ans+=(a[i]+b[pl])*(a[i]+b[pl]);
    for(int i=r;id[i]==pr;i--)ave+=a[i]+b[pr],ans+=(a[i]+b[pr])*(a[i]+b[pr]);
    for(int i=pl+1;i<pr;i++)ave+=s[i]+b[i]*::len,ans+=s_2[i]+2*s[i]*b[i]+::len*b[i]*b[i];
    return ans/len-(ave/len)*(ave/len);
}
int main(){
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
        s[id[i]]+=a[i];
        s_2[id[i]]+=a[i]*a[i];
    }
    while(m--){
        int opt,l,r;
        db k;
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>k;
            add(l,r,k);
        }else if(opt==2){
            printf("%.4f\n",query1(l,r));
        }else{
            printf("%.4f\n",query2(l,r));
        }
    }
}

例题 luogu P1531

  • 当 为 Q 的时候，表示这是一条询问操作，它询问 ID 从 到 （包括 ） 的学生当中，成绩最高的是多少；
  • 当 为 U 的时候，表示这是一条更新操作，如果当前 学生的成绩低于 ，则把 ID 为 的学生的成绩更改为 ，否则不改动。 简单题。

一眼想到 st 表，发现带修改，寄了。

设 为 所在块编号。

我们对每个块去维护最大值 ，修改时就将 修改为 ，同时更新一下 就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,m,mx[N],id[N],a[N],len;
int query(int l,int r){
    int ans=-1;
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)ans=max(ans,a[i]);
        return ans;
    }
    for(int i=l;id[l]==id[i];i++)ans=max(ans,a[i]);
    for(int i=id[l]+1;i<id[r];i++)ans=max(ans,mx[i]);
    for(int i=r;id[r]==id[i];i--)ans=max(ans,a[i]);
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/len+1;
        mx[id[i]]=max(mx[id[i]],a[i]);
    }
    while(m--){
        char opt;
        int l,r;
        cin>>opt>>l>>r;
        if(opt=='U'){
            if(a[l]<r){
                a[l]=r;
                mx[id[l]]=max(mx[id[l]],r);
            }
        }else cout<<query(l,r)<<endl;
    }
}

例题 luogu P2617

给定一个含有 个数的序列 ，需要支持两种操作：

  • Q l r k 表示查询下标在区间 中的第 小的数；
  • C x y 表示将 改为 。

动态区间 kth 板子题。

这玩意儿的静态版本可以用主席树 飞过去（但板子题分块 T 飞了？）。但动态疑似还要套一层线段树。

妈的不会真有人写树套树吧。

考虑静态查询。
我们考虑二分区间第 小值。我们将每次的 算一下 。

怎么算这一坨？
先用 单独存一下每一个块，然后再用一个数组 维护有序的块。
小块暴力统计，大块在 里 upper_bound 就行了。
然后就很板子了。

考虑动态查询。
其实很简单，将 改为 后，再将 里对应的元素修改，重新复制到 里，排序就好了。

#pragma target optimize(O3)
#pragma target optimize(O2)
#pragma target optimize(O1)
#pragma target optimize(Ofast)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int a[N],blk[320][320],siz[320],n,m,id[N],len,sor[320][320],cpy[320];
inline int read(){
    int f=0;char ch=getchar();
    while(ch<48||ch>57)ch=getchar();
    while(ch>47&&ch<58)f=(f<<3)+(f<<1)+(ch^48),ch=getchar();
    return f;
}
inline void print(int x){
    if(x==0){putchar('0');return;}
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
void sorted(int id){
    for(int i=1;i<=siz[id];i++)cpy[i]=blk[id][i];
    sort(cpy+1,cpy+siz[id]+1);
    for(int i=1;i<=siz[id];i++)sor[id][i]=cpy[i];
}
int rk(int l,int r,int x){
    int ans=0;
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++)if(a[i]<=x)ans++;
        return ans;
    }
    for(int i=l;id[l]==id[i];i++)if(a[i]<=x)ans++;
    for(int i=id[l]+1;i<id[r];i++)ans+=upper_bound(sor[i]+1,sor[i]+siz[i]+1,x)-sor[i]-1;
    for(int i=r;id[r]==id[i];i--)if(a[i]<=x)ans++;
    return ans;
}
int kth(int l,int r,int k){
    int L=0,R=1e9+7,ans=-1;
    while(L<=R){
        int mid=(L+R)>>1;
        if(rk(l,r,mid)>=k){
            ans=mid;
            R=mid-1;
            //if(mid==6)cout<<rk(l,r,6)<<endl;
        }else L=mid+1;
    }
    return ans;
}
signed main(){
    n=read();
    m=read();
    len=sqrt(n);
    for(int i=1;i<=n;i++){
        a[i]=read();
        id[i]=(i-1)/len+1;
        blk[id[i]][++siz[id[i]]]=a[i];
    }
    for(int i=1;i<=(n+len-1)/len;i++)sorted(i);
    while(m--){
        char c;
        int l,r,k;
        cin>>c;
        l=read();
        r=read();
        if(c=='C'){
            int p=l-(id[l]-1)*len;
            blk[id[l]][p]=r;
            a[l]=r;
            sorted(id[l]);
            //for(int i=1;i<=siz[id[l]];i++)cout<<sor[id[l]][i]<<' ';
            //cout<<endl;
        }
        else{
            k=read();
            print(kth(l,r,k));
            putchar('\n');
        }
    }
}

例题 luogu P5356

给你一个长为 的序列 ，需要支持 次操作，操作有两种：

  1. 查询区间 的第 小值。
  2. 区间 加上 。 与 P1531 的区别在于此题是区间修改。

依旧简单题。

依旧整体二分。
我们算 时，将 减掉此块对应的懒标记计数即可，整块二分也是同理。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,len=500,a[N],b[N],tag[N];
void sorted(int idx){
    int l=idx*len;
    int r=min((idx+1)*len,n);
    memcpy(b+l,a+l,(r-l)<<2);
    sort(b+l,b+r);
}
void add(int l,int r,int x){
    int L=l/len;
    int R=r/len;
    if(L==R){
        for(int i=l;i<=r;i++) a[i]+=x;
        sorted(L);
        return;
    }
    int ll=(L+1)*len;
    for(int i=l;i<ll;i++) a[i]+=x;
    sorted(L);
    for(int i=L+1;i<R;i++) tag[i]+=x;
    int rr=R*len;
    for(int i=rr;i<=r;i++) a[i]+=x;
    sorted(R);
}
int rk(int l,int r,int x){
    int L=l/len;
    int R=r/len;
    int ans=0;
    if(L==R){
        for(int i=l;i<=r;i++) ans+=a[i]+tag[L]<=x;
        return ans;
    }
    int ll=(L+1)*len;
    for(int i=l;i<ll;i++) ans+=a[i]+tag[L]<=x;
    for(int i=L+1;i<R;i++){
        ans+=upper_bound(b+i*len,b+(i+1)*len,x-tag[i])-b-i*len;
    }
    int rr=R*len;
    for(int i=rr;i<=r;i++) ans+=a[i]+tag[R]<=x;
    return ans;
}
int query(int l,int r,int k){
    int L=-2e4-2e9-1,R=2e9+2e4+1,ans=-1;
    while(L<=R){
        int mid=((long long)L+R)/2;
        if(rk(l,r,mid)>=k){
            ans=mid;
            R=mid-1;
        }else L=mid+1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i*len<n;i++) sorted(i);
    while(m--){
        int opt,l,r,k;
        cin>>opt>>l>>r>>k;
        l--;r--;
        if(opt==2) add(l,r,k);
        if(opt==1) cout<<query(l,r,k)<<'\n';
    }
}

此代码常数巨大，不开 C++98 过不了，测试点几乎是擦着时限过去的。

评论 (0)

还没有评论，来抢沙发吧！
登录 后参与评论
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 新ICP备2026003452号-2
当前版本：V1.7.1