分块的思想可以解决很多问题,比如区间更新,区间求和/单点询问,当然这些问题也可以用线段树或者树状数组解决(而且线段树的时间复杂度相对较低)。
对于某些问题,比如“区间加法,询问区间内小于某个值x的最大元素”,分块是比较方便的。

LOJ 6277 数列分块入门1

区间加法,单点询问。

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,l,r,k,bl,opt,a[N],b[N],f[N];
void add(int l,int r,int k)
{
    for(int i=l;i<=min(r,b[l]*bl);i++)
        a[i]+=k;
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
            a[i]+=k;
    for(int i=b[l]+1;i<=b[r]-1;i++)
        f[i]+=k;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    bl=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/bl+1;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>opt>>l>>r>>k;
        if(opt==0)add(l,r,k);
        else printf("%d\n",a[r]+f[b[r]]);
    }
    return 0;
}

LOJ 6278 数列分块入门2

区间加法,询问区间内小于某个值x的元素个数。

滚动数组 g[ i ][ j ] 表示第 i 块的第 j 个元素,维护这个数组,使其升序排列,便于之后二分查找。

对最左块和最右块的部分元素进行区间加法后,可能会打破原来的升序排列,必须重新排序最左块和最右块。

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
vector<int>g[510];
int n,l,r,k,bl,opt,a[N],b[N],f[N];
void resort(int num)//对第num块内重新排序
{
    g[num].clear();
    for(int i=(num-1)*bl+1;i<=num*bl;i++)
        g[num].push_back(a[i]);
    sort(g[num].begin(),g[num].end());
}
void add(int l,int r,int k)
{
    for(int i=l;i<=min(r,b[l]*bl);i++)//暴力更新最左块内部分元素
        a[i]+=k;
    resort(b[l]);//重新排序最左块
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)//暴力更新最右块内部分元素
            a[i]+=k;
    resort(b[r]);//重新排序最右块
    for(int i=b[l]+1;i<=b[r]-1;i++)
        f[i]+=k;//第i块加上懒标记,之后查询的时候块内元素再加上懒标记
}
int query(int l,int r,int k)
{
    int s=0;
    for(int i=l;i<=min(r,b[l]*bl);i++)
        if(a[i]+f[b[l]]<k)s++;
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
            if(a[i]+f[b[r]]<k)s++;
    for(int i=b[l]+1;i<=b[r]-1;i++)
    {
        int tmp=lower_bound(g[i].begin(),g[i].end(),k-f[i])-g[i].begin();//二分查找第i块内大于等于k-f[i]的第一个元素下标
        s+=tmp;
    }
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    bl=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/bl+1;
        g[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=b[n];i++)
        sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
    {
        cin>>opt>>l>>r>>k;
        if(opt==0)add(l,r,k);
        else printf("%d\n",query(l,r,k*k));
    }
    return 0;
}

LOJ 6279 数列分块入门3

区间加法,询问区间内小于某个值x的前驱(比其小的最大元素)。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[510];
int n,l,r,k,bl,opt,a[N],b[N],f[N];
void resort(int num)
{
    g[num].clear();
    for(int i=(num-1)*bl+1;i<=num*bl;i++)
        g[num].push_back(a[i]);
    sort(g[num].begin(),g[num].end());
}
void add(int l,int r,int k)
{
    for(int i=l;i<=min(r,bl*b[l]);i++)
        a[i]+=k;
    resort(b[l]);
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
            a[i]+=k;
    resort(b[r]);
    for(int i=b[l]+1;i<=b[r]-1;i++)
        f[i]+=k;
}
int query(int l,int r,int k)
{
    int mx=-1;
    for(int i=l;i<=min(r,bl*b[l]);i++)
        if(a[i]+f[b[l]]<k)mx=max(mx,a[i]+f[b[l]]);
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
            if(a[i]+f[b[r]]<k)mx=max(mx,a[i]+f[b[r]]);
    for(int i=b[l]+1;i<=b[r]-1;i++)
    {
        int tmp=lower_bound(g[i].begin(),g[i].end(),k-f[i])-g[i].begin();
        if(tmp>=1)mx=max(mx,g[i][tmp-1]+f[i]);
    }
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    bl=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/bl+1;
        g[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=b[n];i++)
        sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
    {
        cin>>opt>>l>>r>>k;
        if(opt==0)add(l,r,k);
        else printf("%d\n",query(l,r,k));
    }
    return 0;
}

LOJ 6280 数列分块入门4

区间加法,区间求和。

与线段树类似,要开一个懒标记数组f[i] (表示第i块内所有元素本来要加上的值),查询的时候再分块把懒标记加上。

sum[i]表示第i块的和,f[i]表示第i块的懒标记。本题的懒标记数组和sum数组必须要用long long。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,l,r,k,bl,opt,a[N],b[N];
ll f[N],sum[N];//sum[i]表示第i块的和,f[i]表示第i块的懒标记
void add(int l,int r,int k)
{
    for(int i=l;i<=min(r,b[l]*bl);i++)
        {a[i]+=k;sum[b[l]]+=k;}
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
        {a[i]+=k;sum[b[r]]+=k;}
    for(int i=b[l]+1;i<=b[r]-1;i++)
        f[i]+=k;
}
ll query(int l,int r,int mod)
{
    ll s=0;
    for(int i=l;i<=min(r,b[l]*bl);i++)
        s+=(a[i]+f[b[l]])%mod;
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
            s+=(a[i]+f[b[r]])%mod;
    for(int i=b[l]+1;i<=b[r]-1;i++)
        s+=(sum[i]+f[i]*bl)%mod;
    return s%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    bl=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/bl+1;
        sum[b[i]]+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>opt>>l>>r>>k;
        if(opt==0)add(l,r,k);
        else printf("%d\n",query(l,r,k+1));
    }
    return 0;
}

LOJ 6281 数列分块入门5

区间开方,区间求和。

int范围内(x<2^31),一个数x,如果x<1,则开方一次后向下取整为0;如果x>=1,则最多被开方5次后向下取整为1。

无论x大于1还是小于1,开方次数大于等于5次后再开方,值是不变的。

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,l,r,k,bl,opt,a[N],b[N],cnt[N],sum[N];//sum[i]记录第i块的和,cnt[i]表示第i块的开方次数
void update(int l,int r)
{
    if(cnt[b[l]]<5)
        for(int i=l;i<=min(r,bl*b[l]);i++)
        {
            sum[b[l]]-=a[i];
            a[i]=(int)sqrt(a[i]);
            sum[b[l]]+=a[i];
        }
    if(cnt[b[r]]<5&&b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
        {
            sum[b[r]]-=a[i];
            a[i]=(int)sqrt(a[i]);
            sum[b[r]]+=a[i];
        }
    for(int i=b[l]+1;i<=b[r]-1;i++)//遍历中间的整块
    {
        if(cnt[i]<5)
        {
            for(int j=(i-1)*bl+1;j<=i*bl;j++)//遍历第i块内的所有元素a[j],进行开方,更新a[j]和sum[i]
            {
                sum[i]-=a[j];
                a[j]=(int)sqrt(a[j]);
                sum[i]+=a[j];
            }
        }
        cnt[i]++;//第i块的开方次数+1
    }
}
int query(int l,int r)
{
    int s=0;
    for(int i=l;i<=min(r,b[l]*bl);i++)
        s+=a[i];
    if(b[l]!=b[r])
        for(int i=(b[r]-1)*bl+1;i<=r;i++)
            s+=a[i];
    for(int i=b[l]+1;i<=b[r]-1;i++)
        s+=sum[i];
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    bl=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=(i-1)/bl+1;
        sum[b[i]]+=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>opt>>l>>r>>k;
        if(opt==0)update(l,r);
        else printf("%d\n",query(l,r));
    }
    return 0;
}