题解：P13978 数列分块入门 3

· · 题解

思路

题目要求对一个序列进行一下两种操作：

  1. 将位于 [l, r] 的之间的数字都加 c。
  2. 询问 [l,r] 中 c 的前驱的值（不存在则输出 −1）。 \\

并且本题需要一种高效的算法来同时完成这两种操作，这里使用分块。

什么是分块

分块是一种非常优雅的暴力，通过对数列进行分段，然后对每段单独求解，对每段的答案合并就是最终的答案。\\ 具体的，假如我们要求区间 [l,r] 的总和，那么我们将序列按每 len 个元素一块进行分块，并记录每块的区间和

sum_i$。这时候会遇到一下两种情况：$\\
  2. # 如何建块 通常情况下，在建块时，我们需要完成以下任务： - 确定块的长度和数量。 - 确定每个块的左右边界。 - 标记每个元素属于那个块。 - 维护每个块的信息。

具体要维护那些信息，每到题目都是不一样的，比如这题，我们需要对块内的元素排序，以便来二分查找。但是前三条都是必要的，具体代码如下：

const int maxn=2e5+5;
const int maxm=450;
int n,m,a[maxn];
int in[maxn],L[maxm],R[maxm],tag[maxm];
int len,cnt;//块长和块数
vector<int> v[maxm];//每个块内排序后的元素
void resort(int x)//对每个块重新排序
{
    v[x].clear();
    for(int i=L[x];i<=R[x];i++) v[x].push_back(a[i]);
    sort(v[x].begin(),v[x].end());
}
void init()
{
    len=cnt=sqrt(n);
    if(len*cnt<n) cnt++;//计算块长和块数
    for(int i=1;i<=cnt;i++)
     {
        L[i]=R[i-1]+1;
        R[i]=i*len;
     }
    R[cnt]=n;//左右边界计算
    for(int i=1;i<=cnt;i++)
     {
        for(int j=L[i];j<=R[i];j++) in[j]=i;//标记每个元素属于那个块。
        resort(i); 
     }   
}

建完了块之后，我们就需要想如何实现题目要求的两种操作。

区间修改

对于不完整的块，直接在原数组中修改即可。但如果时完整的块，我们再去依次修改就很消耗时间，这时候我们就需要用到线段树中懒标记的思想，用一个数组 tag 来标记整个块中加的数，那么每个数它实际的值就变成了 a_i+tag_{in_i}，这一点需要注意。\\

那么完整代码如下：

void add(int l,int r,int x)
{
    int p=in[l],q=in[r];
    if(p==q)//特判在同一个块内的情况
     {
        for(int i=l;i<=r;i++) a[i]+=x;
        resort(p);//重新排序
     }
    else
     {
        for(int i=l;i<=R[p];i++) a[i]+=x;
        for(int i=L[q];i<=r;i++) a[i]+=x;
        resort(p);resort(q); //重新排序
        for(int i=p+1;i<=q-1;i++) tag[i]+=x;
     } 
}

区间查询

题目要求区间内某个值 x 的前驱（比其小的最大元素）。可以用 STL 中的lower_bound来快速计算。还是一样，对于不完整的块，还是暴力求解。对于完整的块，直接对块内的元素二分查找即可。\\

具体代码如下：

int query(int l,int r,int c)
{
    int ans=-1e18,p=in[l],q=in[r];
    if(p==q)
     {
        for(int i=l;i<=r;i++)
         if(a[i]+tag[p]<c) ans=max(ans,a[i]+tag[p]);
        return (ans==-1e18)?-1:ans;
     }
    for(int i=l;i<=R[p];i++)
     if(a[i]+tag[p]<c) ans=max(ans,a[i]+tag[p]);
    for(int i=L[q];i<=r;i++)
     if(a[i]+tag[q]<c) ans=max(ans,a[i]+tag[q]);
    for(int i=p+1;i<=q-1;i++)
     {
        auto it=lower_bound(v[i].begin(),v[i].end(),c-tag[i]);
        if(it!=v[i].begin()) ans=max(ans,*(--it)+tag[i]);
     }
    return (ans==-1e18)?-1:ans;
}