分块算法-例题

一、算法介绍：

首先，分块是一种线性的暴力数据结构。
其基本思想是将一段序列，分成一定数量的块，每一块有一个长度，表示一段区间。对于区间操作，通过对完整块的整体操作和对不完整块的暴力操作而使复杂度尽可能的低。当块的大小设为 sqrt(n)时间复杂度最低。
数据量在1e5之内，时间复杂度为o(n*√n)时算法可在1s内通过，时间复杂度为o(n*√n*log(n))时算法可在2s内通过。
与树状数组和线段树相比，分块简便易写，方便调试，容易理解，且具有较大的可拓展性。

二、例题分析：

1.分块一：https://loj.ac/problem/6277

利用分块算法实现数据的区间修改和单点查询o(n*√n)

#include <bits/stdc++.h>

using namespace std;

const int N=5e4+5;

int n;
int sqr;
int a[N],tag[N],bel[N];    //a单个数据点，tag数据块上的加法标记，bel数据点所属分块

void Add(int l,int r,int v)
{
    for(int i=l;i<=min(r,bel[l]*sqr);i++) a[i]+=v;    //暴力处理左边不完整区间
    if(bel[r]==bel[l]) return;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++) a[i]+=v;     //暴力处理右边不完整区间
    for(int i=bel[l]+1;i<=bel[r]-1;i++) tag[i]+=v;    //完整区间处理，打标记
}

int main()
{
    cin>>n;
    sqr=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        bel[i]=(i-1)/sqr+1;    //计算数据点属于哪个分块
    }
    for(int i=1;i<=n;i++)
    {
        int op,l,r,v;
        scanf("%d%d%d%d",&op,&l,&r,&v);
        if(op==0) Add(l,r,v);
        else
        {
            printf("%d\n",a[r]+tag[bel[r]]);
        }
    }
}

2. 分块二：https://loj.ac/problem/6278

区间加法 & 查询某一区间内小于值x的数据个o(n*√n*log(n))

#include <bits/stdc++.h>

using namespace std;

const int N=5e4+5;

int n;
int sqr;
int a[N],bel[N],tag[N];
vector<int>vis[505];    //利用动态数组储存分块数据，用lower_bound()进行二分查询

void Reset(int l)    //不完整区间修改tag标记无效，需要对区间中所有数进行重构和排序
{
    int j=bel[l];
    vis[j].clear();
    for(int i=(j-1)*sqr+1;i<=min(n,j*sqr);i++)
    {
        vis[j].push_back(a[i]);
    }
    sort(vis[j].begin(), vis[j].end());
}

void Add(int l,int r,int v)
{
    for(int i=l; i<=min(r,bel[l]*sqr); i++) a[i]+=v;    //不完整区间处理
    Reset(l);
    if(bel[l]==bel[r]) return;
    for(int i=(bel[r]-1)*sqr+1; i<=r; i++) a[i]+=v;
    Reset(r);


    for(int i=bel[l]+1;i<=bel[r]-1;i++)    //完整区间处理
    {
        tag[i]+=v;
    }
}

int Query(int l,int r,int v)
{
    int re=0;
    for(int i=l;i<=min(r,bel[l]*sqr);i++)
    {
        if(a[i]+tag[bel[l]]<v) re++;
    }
    if(bel[l]==bel[r]) return re;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++)
    {
        if(a[i]+tag[bel[r]]<v) re++;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
    {
        int tmp=lower_bound(vis[i].begin(),vis[i].end(),v-tag[i])-vis[i].begin();    //log(n)的来历
        re+=tmp;
    }
    return re;
}

int main()
{
    cin>>n;
    sqr=(int)sqrt(n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        bel[i]=(i-1)/sqr+1;
        vis[bel[i]].push_back(a[i]);    //储存分块数据
    }
    for(int i=1; i<=(n-1)/sqr+1; i++)
    {
        sort(vis[i].begin(), vis[i].end());    //将每一个分块数据升序排列
    }
    int op,l,r,v;
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d%d",&op,&l,&r,&v);
        if(op==0) Add(l,r,v);
        else
        {
            printf("%d\n",Query(l,r,v*v));
        }
    }

}

3. 分块三：https://loj.ac/problem/6279

区间加法 & 询问某区间内小于x的最大值

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n;
int sqr;
int a[N],bel[N],tag[N];
vector<int>vis[505];

void Reset(int l)
{
    int j=bel[l];
    vis[j].clear();
    for(int i=(j-1)*sqr+1;i<=min(n,j*sqr);i++)
    {
        vis[j].push_back(a[i]);
    }
    sort(vis[j].begin(), vis[j].end());
}

void Add(int l,int r,int v)
{
    for(int i=l;i<=min(r,bel[l]*sqr);i++) a[i]+=v;
    Reset(l);
    if(bel[l]==bel[r]) return;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++) a[i]+=v;
    Reset(r);
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
    {
        tag[i]+=v;
    }
}

int Query(int l,int r,int v)        //与分块二不同的地方
{
    int ans=-0x3f3f3f3f;
    for(int i=l;i<=min(r,bel[l]*sqr);i++)
        if(a[i]+tag[bel[l]]<v)
        ans=max(ans,a[i]+tag[bel[l]]);
    if(bel[l]==bel[r]) return ans;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++)
        if(a[i]+tag[bel[r]]<v)
        ans=max(ans,a[i]+tag[bel[r]]);
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
    {
        int tmp=lower_bound(vis[i].begin(),vis[i].end(),v-tag[i])-vis[i].begin();
        if(tmp==0) continue;
        else
        {
            ans=max(ans,vis[i][tmp-1]+tag[i]);
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    sqr=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        bel[i]=(i-1)/sqr+1;
        vis[bel[i]].push_back(a[i]);
    }
    for(int i=1;i<=(n-1)/sqr+1;i++)
    {
        sort(vis[i].begin(), vis[i].end());
    }
    int op,l,r,v;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&op,&l,&r,&v);
        if(op==0) Add(l,r,v);
        else
        {
            int ans=Query(l,r,v);
            if(ans==-0x3f3f3f3f) printf("%d\n",-1);
            else printf("%d\n",ans);
        }
    }
}

4. 分块四：https://loj.ac/problem/6280

区间加法 & 区间求和

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

typedef long long LL;

int n,sqr;
LL a[N],tag[N],sum[N];    //sum用于储存块内数据和，方便查询
int bel[N];

//左右不完整区间更新a[i],更新sum; 完整区间更新tag

void Add(int l,int r,int v)
{
    for(int i=l;i<=min(r,bel[l]*sqr);i++)
    {
        a[i]+=v;
        sum[bel[l]]+=v;
    }
    if(bel[l]==bel[r]) return;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++)
    {
        a[i]+=v;
        sum[bel[r]]+=v;
    }
    for(int i=bel[l]+1;i<=bel[r]-1;i++)
    {
        tag[i]+=v;
    }
}
LL Query(int l,int r)
{
    LL ans=0;
    for(int i=l;i<=min(r,bel[l]*sqr);i++) ans+=a[i]+tag[bel[l]];
    if(bel[l]==bel[r]) return ans;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++) ans+=a[i]+tag[bel[r]];
    for(int i=bel[l]+1;i<=bel[r]-1;i++) ans+=tag[i]*sqr+sum[i];
    return ans;
}
int main()
{
    cin>>n;
    sqr=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        bel[i]=(i-1)/sqr+1;
        sum[bel[i]]+=a[i];
    }
    int op,l,r,v;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&op,&l,&r,&v);
        if(op==0) Add(l,r,v);
        else
        {
            printf("%d\n",Query(l,r)%(v+1));
        }
    }
}

5. 分块五：https://loj.ac/problem/6281

对某一区间所有数进行开方 & 区间和查询

#include <bits/stdc++.h>

using namespace std;

const int N=5e4+5;

typedef long long LL;

int n,sqr;
LL a[N],sum[N];    //sum用于储存数据块内值的和
int bel[N];
bool avl[N];       //判断某一数据块是否还有必要进行开方处理(0,1)

void Update(int l,int r)
{

    if(avl[bel[l]])                         //暴力左右不完整区间
    for(int i=l;i<=min(r,bel[l]*sqr);i++)
    {
        sum[bel[l]]-=a[i];
        a[i]=sqrt(a[i]);
        sum[bel[l]]+=a[i];
    }
    if(bel[l]==bel[r]) return;
    if(avl[bel[r]])
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++)
    {
        sum[bel[r]]-=a[i];
        a[i]=sqrt(a[i]);
        sum[bel[r]]+=a[i];
    }



    for(int i=bel[l]+1;i<=bel[r]-1;i++)      //对完整区间进行数据块重构
    {
        if(avl[i])
        {
            avl[i]=false;
            sum[i]=0;
            for(int j=(i-1)*sqr+1;j<=min(n,i*sqr);j++)
            {
                a[j]=sqrt(a[j]);
                sum[i]+=a[j];
                if(a[j]>1) avl[i]=true;
            }
        }
    }
}

LL Query(int l,int r)
{
    LL re=0;
    for(int i=l;i<=min(r,bel[l]*sqr);i++) re+=a[i];
    if(bel[l]==bel[r]) return re;
    for(int i=(bel[r]-1)*sqr+1;i<=r;i++) re+=a[i];
    for(int i=bel[l]+1;i<=bel[r]-1;i++) re+=sum[i];
    return re;
}

int main()
{
    cin>>n;
    sqr=(int)sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        bel[i]=(i-1)/sqr+1;
        sum[bel[i]]+=a[i];
        if(a[i]>1) avl[bel[i]]=true;
    }
    int op,l,r,v;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&op,&l,&r,&v);
        if(op==0) Update(l,r);
        else
        {
            printf("%lld\n",Query(l,r));
        }
    }
}

分块算法-例题

一、算法介绍：

二、例题分析：

继续阅读

【数据结构】医院选址

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

[转]ISUP信令的IAM消息详细内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

hdu 4741 Save Labman No.004（计算几何） Save Labman No.004

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希