数列分块

· · 算法·理论

哎数列分块学的太烂了，重学一下吧。

这篇文章主要面向数列分块的初学者，所以写的比较详细。

为表公平，所有代码都使用下面的语言环境提交：

若无特殊说明，默认 n,Q 同阶。保证代码输入输出只用了 cin/cout，且关闭同步流。

数列分块的简单介绍

什么是数列分块

数列分块，就是把一个数组分为若干个块来维护，每次如果修改跨过了一整个块就在这个块上打标记（tag），否则就暴力修改这个块。

在多数题目中，B=\sqrt{n} 是一个很好的块长。

数列分块的操作

建立树状数组

记 B 为块长。对于每个块，块的左右端点是好求的。具体的，对于第 i 个块，它的左端点为 B(i-1)+1，右端点为 \min(n,Bi)。

先求出每个块的左右端点，然后令这一个块的所有元素的所属块编号（belong）为这个块即可。

同时，还可以在这个函数内直接处理初始时和块有关的一些信息。以「数列分块入门 4」（区间加区间求和）为例，处理和块有关的信息（区间和 sum）的部分被高亮显示。

:::info[Code]

void build()
{
    blksz=sqrt(n);//这里是块的大小
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;//求左右端点
        if(ed[i]>=n)//最后一个块
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;//确定每个元素的所属块变化
            sum[i]+=a[j];//处理初始时每个块的信息
        }
        sz[i]=ed[i]-st[i]+1;//块的实际大小
    }
    return;
}

:::

下放标记

对于大部分题目，如果要进行散块暴力修改，那么就需要先下放这个块的标记来更新块内所有元素的值再进行修改。

下放的过程是很好理解的，相当于就是做 B 次单点查询来更新所有元素的值。下放完记得重置标记。

下面是以「数列分块入门 7」为例的代码。

:::info[Code]

//数列分块入门 7 中，更新 x 时 x <- (tag1*x+tag2)%mod
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++)
    {
        a[i]=(tag1[p]*a[i]+tag2[p])%mod;//更新所有元素
    }
    tag1[p]=1;
    tag2[p]=0;//重置标记
    return;
}

:::

区间修改

对于 [l,r] 的区间修改，有两种情况：

  1. - 此时先下放这个块的标记（如果需要），再对 $[l,r]$ 内的所有元素暴力更新即可。
  2. - 此时先暴力更新 $l$ 到 $l$ 所在块的末尾，$r

    所在块的开头到 r 的所有位置（更新散块）。更新时如有需要要先下放标记。

    • 再对 [l,r] 之间的所有块做整块的更新（更新整块）。

这样，每次最多修改 \frac{n}{B} 个整块和 2B 个元素。假设 B=\sqrt{n}，每次修改 O(1)，那么整体复杂度就是 O(\sqrt{n})。

下面是以「数列分块入门 4」为例的代码。

:::info[Code]

void add(int l,int r,int d)
{
    if(belong[l]==belong[r])//l,r 在一个块
    {
        //如果有需要的话在这里下放标记
        for(int i = l; i <= r; i++)//暴力更新所有元素
        {
            a[i]+=d;
            sum[belong[l]]+=d;
        }
        return;
    }
    //l,r 不在一个块
    //如果有需要的话在这里下放标记
    for(int i = l; i <= ed[belong[l]]; i++)//更新 l 所在散块
    {
        a[i]+=d;
        sum[belong[l]]+=d;
    }
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;//更新整块
    //如果有需要的话在这里下放标记
    for(int i = st[belong[r]]; i <= r; i++)//更新 r 所在散块
    {
        a[i]+=d;
        sum[belong[r]]+=d;
    }
    return;
}

:::

区间查询

和修改的原理是类似的哦！

对于 [l,r] 的区间查询，有两种情况：

  1. - 此时先下放这个块的标记（如果需要），再对 $[l,r]$ 内的所有元素暴力查询即可。
  2. - 此时先暴力查询 $l$ 到 $l$ 所在块的末尾，$r

    所在块的开头到 r 的所有位置（查询散块）。查询时如有需要要先下放标记。

    • 再对 [l,r] 之间的所有块做整块的查询（查询整块）。

这样，每次最多查询 \frac{n}{B} 个整块和 2B 个元素。假设 B=\sqrt{n}，每次查询 O(1)，那么整体复杂度就也是 O(\sqrt{n})。

下面是以「数列分块入门 4」为例的代码。

:::info[Code]

int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])//l,r 在一个块
    {
        //如果有需要的话在这里下放标记
        for(int i = l; i <= r; i++) ret+=tag[belong[l]]+a[i];//暴力查询所有元素
        return ret%x;
    }
    //l,r 不在一个块
    //如果有需要的话在这里下放标记
    for(int i = l; i <= ed[belong[l]]; i++) ret+=tag[belong[l]]+a[i];//查询 l 所在散块
    for(int i = belong[l]+1; i < belong[r]; i++) ret+=sum[i]+tag[i]*sz[i];//查询整块
    //如果有需要的话在这里下放标记
    for(int i = st[belong[r]]; i <= r; i++) ret+=tag[belong[r]]+a[i];//查询 r 所在散块
    return ret%x;
}

:::

数列分块确定块长的技巧

IOI2017中国国家候选队论文集 《非常规大小分块算法初探》

若时间复杂度能写成类似 O(\alpha+\beta) 的形式，其中 \alpha 随 B 增大而增大，\beta 随 B 增大而减小，则解 \alpha=\beta 即可解出 B 的最优值。

更进一步地，如果你确信每次操作的个数是 \alpha(B)+\beta(B) 并想得到更精确的块长，解 \alpha'(B)+\beta'(B)=0 即可。

例题：数列分块入门 & AAL001

数列分块入门 1

维护一个支持区间加，单点查值的数组。

n\leq 3\times 10^5

本题的懒标记只需维护一个区间加的懒标记即可。

:::success[参考代码 176ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
#define int long long
int n,a[500005],op,l,r,x;
int blksz,blknum,belong[500005],tag[500005],st[5005],ed[5005],sz[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++) a[i]+=d;
        return;
    }
    for(int i = l; i <= ed[belong[l]]; i++) a[i]+=d;
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    for(int i = st[belong[r]]; i <= r; i++) a[i]+=d;
    return;
}
int query(int x)
{
    return a[x]+tag[belong[x]];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<query(r)<<'\n';
    }
    return 0;
}

:::

数列分块入门 2

维护一个支持区间加，区间查 \leq x 的数的个数的数组。

n\leq 2\times 10^5

首先修改是简单的。

对于查询，散块直接暴力统计，现在的问题变成了怎么快速查询一个整块内 \leq x 的数的个数。

我们发现，如果块内有序，这个东西可以用 lower_bound 做到 O(\log B)。

因此我们对于每个块，都维护一个块内所有元素排序后的数组，修改/查询时对于两端暴力重构这个数组，对于中间，用 tag 对 x 做差来抵消误差即可。

:::success[参考代码 1 11.09s] pushdown：下放标记

pushup：暴力重构这个块

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[300005],op,l,r,x;
int blksz,blknum,belong[300005],st[5005],ed[5005],sz[5005];
int tag[5005];
int num[300005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            num[j]=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
        sort(num+st[i],num+ed[i]+1);
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) a[i]+=tag[p];
    tag[p]=0;
    return;
}
void pushup(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) num[i]=a[i];
    sort(num+st[p],num+ed[p]+1);
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]+=d;
        pushup(belong[l]);
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]+=d;
    pushup(belong[l]);
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]+=d;
    pushup(belong[r]);
    return;
}
int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) ret+=(a[i]<x);
        pushup(belong[l]);
        return ret;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) ret+=(a[i]<x);
    pushup(belong[l]);
    for(int i = belong[l]+1; i < belong[r]; i++) ret+=lower_bound(num+st[i],num+ed[i]+1,x-tag[i])-(num+st[i]);
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) ret+=(a[i]<x);
    pushup(belong[r]);
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<query(l,r,x*x)<<'\n';
    }
    return 0;
}

:::

怎么这么慢？

我们考虑上面下放的过程，注意查询时的下放标记其实是没有必要的，可以沿用整块的偏移做法，因此我们只需要在修改时下放标记即可。

此时时间复杂度从 O(B\log B+\frac{n}{B})- O(B\log B+\frac{n}{B} \log B) 下降到 O(B\log B+\frac{n}{B})- O(B+\frac{n}{B} \log B)。

:::success[参考代码 2 5.32s]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[200005],op,l,r,x;
int blksz,blknum,belong[200005],st[5005],ed[5005],sz[5005];
int tag[5005];
int num[200005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            num[j]=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
        sort(num+st[i],num+ed[i]+1);
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) a[i]+=tag[p];
    tag[p]=0;
    return;
}
void pushup(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) num[i]=a[i];
    sort(num+st[p],num+ed[p]+1);
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]+=d;
        pushup(belong[l]);
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]+=d;
    pushup(belong[l]);
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]+=d;
    pushup(belong[r]);
    return;
}
int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++) ret+=((a[i]+tag[belong[l]])<x);
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++) ret+=((a[i]+tag[belong[l]])<x);
    for(int i = belong[l]+1; i < belong[r]; i++) ret+=lower_bound(num+st[i],num+ed[i]+1,x-tag[i])-(num+st[i]);
    for(int i = st[belong[r]]; i <= r; i++) ret+=((a[i]+tag[belong[r]])<x);
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<query(l,r,x*x)<<'\n';
    }
    return 0;
}

:::

同时推荐块长：B=\sqrt{\frac{n}{5}}。我也不知道为什么小块长跑这么快。

:::success[参考代码 3 3.24s]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[200005],op,l,r,x;
int blksz,blknum,belong[200005],st[5005],ed[5005],sz[5005];
int tag[5005];
int num[200005];
void build()
{
    blksz=sqrt(n/5);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            num[j]=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
        sort(num+st[i],num+ed[i]+1);
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) a[i]+=tag[p];
    tag[p]=0;
    return;
}
void pushup(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) num[i]=a[i];
    sort(num+st[p],num+ed[p]+1);
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]+=d;
        pushup(belong[l]);
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]+=d;
    pushup(belong[l]);
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]+=d;
    pushup(belong[r]);
    return;
}
int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++) ret+=((a[i]+tag[belong[l]])<x);
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++) ret+=((a[i]+tag[belong[l]])<x);
    for(int i = belong[l]+1; i < belong[r]; i++) ret+=lower_bound(num+st[i],num+ed[i]+1,x-tag[i])-(num+st[i]);
    for(int i = st[belong[r]]; i <= r; i++) ret+=((a[i]+tag[belong[r]])<x);
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<query(l,r,x*x)<<'\n';
    }
    return 0;
}

:::

数列分块入门 3

维护一个支持区间加，区间查 x 的前驱的数组。

n\leq 2\times 10^5

考虑「数列分块入门 2」带来的启示。可以沿用维护一个有序数组的做法，区间内 x 的前驱就相当于是每个块内 x 的前驱的最大值。

对于每个整块查前驱直接 lower_bound，散块直接暴力处理即可。

:::success[参考代码 1 6.33s]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[200005],op,l,r,x;
int blksz,blknum,belong[200005],st[5005],ed[5005],sz[5005];
int tag[5005];
int num[200005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            num[j]=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
        sort(num+st[i],num+ed[i]+1);
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) a[i]+=tag[p];
    tag[p]=0;
    return;
}
void pushup(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) num[i]=a[i];
    sort(num+st[p],num+ed[p]+1);
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]+=d;
        pushup(belong[l]);
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]+=d;
    pushup(belong[l]);
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]+=d;
    pushup(belong[r]);
    return;
}
int query(int l,int r,int x)
{
    int ret=-1145141919810;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++)
        {
            if(a[i]+tag[belong[l]]<x) ret=max(ret,a[i]+tag[belong[l]]);
        }
        if(ret==-1145141919810) ret=-1;
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        if(a[i]+tag[belong[l]]<x) ret=max(ret,a[i]+tag[belong[l]]);
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        auto it=lower_bound(num+st[i],num+ed[i]+1,x-tag[i]);
        if(it!=(num+st[i]))
        {
            it--;
            ret=max(ret,(*it)+tag[i]);
        }
    }
    for(int i = st[belong[r]]; i <= r; i++)
    {
        if(a[i]+tag[belong[r]]<x) ret=max(ret,a[i]+tag[belong[r]]);
    }
    if(ret==-1145141919810) ret=-1;
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<query(l,r,x)<<'\n';
    }
    return 0;
}

:::

同样地，调小块长也可以让代码稍许优秀一些。

推荐 B=\sqrt{\frac{n}{6}}。

:::success[参考代码 2 3.23s]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[200005],op,l,r,x;
int blksz,blknum,belong[200005],st[5005],ed[5005],sz[5005];
int tag[5005];
int num[200005];
void build()
{
    blksz=sqrt(n/6);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            num[j]=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
        sort(num+st[i],num+ed[i]+1);
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) a[i]+=tag[p];
    tag[p]=0;
    return;
}
void pushup(int p)
{
    for(int i = st[p]; i <= ed[p]; i++) num[i]=a[i];
    sort(num+st[p],num+ed[p]+1);
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]+=d;
        pushup(belong[l]);
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]+=d;
    pushup(belong[l]);
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]+=d;
    pushup(belong[r]);
    return;
}
int query(int l,int r,int x)
{
    int ret=-1145141919810;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++)
        {
            if(a[i]+tag[belong[l]]<x) ret=max(ret,a[i]+tag[belong[l]]);
        }
        if(ret==-1145141919810) ret=-1;
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        if(a[i]+tag[belong[l]]<x) ret=max(ret,a[i]+tag[belong[l]]);
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        auto it=lower_bound(num+st[i],num+ed[i]+1,x-tag[i]);
        if(it!=(num+st[i]))
        {
            it--;
            ret=max(ret,(*it)+tag[i]);
        }
    }
    for(int i = st[belong[r]]; i <= r; i++)
    {
        if(a[i]+tag[belong[r]]<x) ret=max(ret,a[i]+tag[belong[r]]);
    }
    if(ret==-1145141919810) ret=-1;
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<query(l,r,x)<<'\n';
    }
    return 0;
}

:::

数列分块入门 4

猜你想搜：P3372 【模板】线段树 1

维护一个支持区间加，区间求和的数组。

n\leq 3\times 10^5

和「数列分块入门 1」本质相同，但是查询可能会跨块，对于一整块的查询，维护一下这一个块内所有元素的和就可以了。

:::success[参考代码 324ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
#define int long long
int n,a[500005],op,l,r,x;
int blksz,blknum,belong[500005],tag[500005],sum[500005],st[5005],ed[5005],sz[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            sum[i]+=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++)
        {
            a[i]+=d;
            sum[belong[l]]+=d;
        }
        return;
    }
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        a[i]+=d;
        sum[belong[l]]+=d;
    }
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]+=d;
    for(int i = st[belong[r]]; i <= r; i++)
    {
        a[i]+=d;
        sum[belong[r]]+=d;
    }
    return;
}
int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++) ret+=tag[belong[l]]+a[i];
        return ret%x;
    }
    for(int i = l; i <= ed[belong[l]]; i++) ret+=tag[belong[l]]+a[i];
    for(int i = belong[l]+1; i < belong[r]; i++) ret+=sum[i]+tag[i]*sz[i];
    for(int i = st[belong[r]]; i <= r; i++) ret+=tag[belong[r]]+a[i];
    return ret%x;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add(l,r,x);
        else cout<<(query(l,r,x+1)+x+1)%(x+1)<<'\n';
    }
    return 0;
}

:::

数列分块入门 5

猜你想搜：P4145 上帝造题的七分钟 2 / 花神游历各国

维护一个支持区间开方，区间求和的数组。

n\leq 3\times 10^5

经典结论：

给定一个数 x\geq 2，每次 x\gets \lfloor \sqrt{x} \rfloor，那么 O(\log \log x) 次操作后 x\leq 1。

也即一个数至多被操作 O(\log \log x) 次。

每次处理时，如果一个块内所有数都 \leq 1，那么修改这个块就是没有效果的。此时可以直接跳过这个块不进行修改。

具体地，对于每个块额外维护一个标记，表示这个块内还有几个元素 >1。当数量 =0 时即可跳过这个块。

:::success[参考代码 232ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
#define int long long
int n,a[300005],op,l,r;
int blksz,blknum,belong[300005];
int sum[5005],rem[5005],st[5005],ed[5005],sz[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            sum[i]+=a[j];
            if(a[j]>1) rem[i]++;
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
void update(int l,int r)
{
    if(belong[l]==belong[r])
    {
        if(rem[belong[l]])
        {
            for(int i = l; i <= r; i++)
            {
                if(a[i]<=1) rem[belong[l]]++;
                sum[belong[l]]-=a[i];
                a[i]=sqrt(a[i]);
                sum[belong[l]]+=a[i];
                if(a[i]<=1) rem[belong[l]]--;
            }
        }
        return;
    }
    if(rem[belong[l]])
    {
        for(int i = l; i <= ed[belong[l]]; i++)
        {
            if(a[i]<=1) rem[belong[l]]++;
            sum[belong[l]]-=a[i];
            a[i]=sqrt(a[i]);
            sum[belong[l]]+=a[i];
            if(a[i]<=1) rem[belong[l]]--;
        }
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        if(rem[i]==0) continue;
        for(int j = st[i]; j <= ed[i]; j++)
        {
            if(a[j]<=1) rem[i]++;
            sum[i]-=a[j];
            a[j]=sqrt(a[j]);
            sum[i]+=a[j];
            if(a[j]<=1) rem[i]--;
        }
    }
    if(rem[belong[r]])
    {
        for(int i = st[belong[r]]; i <= r; i++)
        {
            if(a[i]<=1) rem[belong[r]]++;
            sum[belong[r]]-=a[i];
            a[i]=sqrt(a[i]);
            sum[belong[r]]+=a[i];
            if(a[i]<=1) rem[belong[r]]--;
        }
    }
    return;
}
int query(int l,int r)
{
    int ret=0;
    if(belong[l]==belong[r])
    { 
        for(int i = l; i <= r; i++) ret+=a[i];
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++) ret+=a[i];
    for(int i = belong[l]+1; i < belong[r]; i++) ret+=sum[i];
    for(int i = st[belong[r]]; i <= r; i++) ret+=a[i];
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r;
        if(op==0) update(l,r);
        else cout<<query(l,r)<<'\n';
    }
    return 0;
}

:::

同时，下面给出了一份由「上帝造题的七分钟 2 / 花神游历各国」修改而来的线段树代码，线段树的时间居然是分块的整整三倍，由此可见分块实力之强悍！欧耶！🎉🎉🎉

:::warning[线段树 696ms]

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct pp
{
    int l,r,dat;
    bool canskip;
};
pp t[1200005];
int n,m,a[300005],x,y;
void pushup(int p)
{
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
    if(t[p*2].canskip&&t[p*2+1].canskip) t[p].canskip=1;
}
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r)
    {
        t[p].dat=a[l];
        if(a[l]<=1) t[p].canskip=1;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
void update(int p,int l,int r)
{
    if(t[p].canskip) return;
    if(t[p].l==t[p].r)
    {
        t[p].dat=sqrt(t[p].dat);
        if(t[p].dat<=1) t[p].canskip=1;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) update(p*2,l,r);
    if(r>mid) update(p*2+1,l,r);
    pushup(p);
}
int query(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        return t[p].dat;
    }
    int mid=(t[p].l+t[p].r)/2,ret=0;
    if(l<=mid) ret+=query(p*2,l,r);
    if(r>mid) ret+=query(p*2+1,l,r);
    return ret;
}
signed main()
{
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build(1,1,n);
    for(int i = 1; i <= n; i++)
    {
        cin>>m>>x>>y;
        if(m)
        {
            cout<<query(1,x,y)<<'\n';
        }
        else
        {
            update(1,x,y);
        }
    }
}

:::

数列分块入门 6

维护一个支持单点插入，单点查值的数组。

n\leq 3\times 10^5

先介绍一种素质低下的做法。

考虑平板电视里面有个东西叫 rope 支持插入和查值操作。直接用 rope 做即可。

::::error[素质低下写法 1.31s]

GPT 说这个东西是 O(n\log n) 的，但是我没查到资料表明这个真的是 \log 的。

下面给出 rope 的官方文档：

Detailed Description
template<class _CharT, class _Alloc>
class __gnu_cxx::rope< _CharT, _Alloc >
This is an SGI extension.

Todo:
  Doc me! See docs/doxygen/TODO and http://gcc.gnu.org/ml/libstdc++/2002-02/msg00003.html for more.

Definition at line 1468 of file rope.

:::info[中文翻译]

详细信息
template<class _CharT, class _Alloc>
class __gnu_cxx::rope< _CharT, _Alloc >

这是一个 SGI 扩展。

待办：
    在这里写文档！详见 docs/doxygen/TODO 和 http://gcc.gnu.org/ml/libstdc++/2002-02/msg00003.html。

定义于 rope 的第 1468 行。

::: 只有聪明的人才能看懂。

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
//#define int long long
int n,op,l,r,x;
rope<int> rp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    rp.append(0);
    for(int i = 1; i <= n; i++)
    {
        cin>>x;
        rp.append(x);
    }
    for(int i = 1; i <= n; i++)
    {
        cin>>op;
        if(op==0)
        {
            cin>>l>>r;
            rp.insert(l,r);
        }
        else
        {
            cin>>x;
            cout<<rp[x]<<'\n';
        }
    }
    return 0;
}

::::

接下来再给出这个东西的正经做法。

考虑最简单的暴力，插入操作就直接插入到块中，用 `vector` 来维护。

但是我们可以不断在同一个块内差，这样分块那优美的结构就爆炸了！

于是我们有两种优化思路：

- 定期重构：每 $O(\sqrt{n})$ 个操作暴力重建所有块来维持形态。
- 块状链表：若插入后块的大小 $\geq 2\sqrt{n}$ 就把这个块分裂成两个块来维持形态。

容易证明两种优化的复杂度都是 $O(n\sqrt{n})$ 的。

如果你写定期重构，记得把重构间隔调大一点，例如 $20\sqrt{n}$，要不然你的代码耗时会飞起来。下面给出定期重构的参考代码。

:::success[参考代码 [282ms](https://www.luogu.com.cn/record/304444499)]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
#define int long long
int n,rn,a[600005],b[600005],op,l,r,x,sn;
int blksz,blknum,st[5005],ed[5005],sz[5005];
vector<int> v[5005];
int rebuild,rebcnt;
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        v[i].clear();
        v[i].push_back(0);
        for(int j = st[i]; j <= ed[i]; j++)
        {
            v[i].push_back(a[j]);
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
void expand()
{
    n=0;
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = 1; j < v[i].size(); j++)
        {
            n++;
            a[n]=v[i][j];
        }
    }
    return;
}
void add(int l,int x)
{
    int nsz=0;
    for(int i = 1; i <= blknum; i++)
    {
        nsz+=v[i].size()-1;
        if(nsz>=l)
        {
            nsz-=v[i].size()-1;
            nsz=l-nsz;
            v[i].insert(v[i].begin()+nsz,x);
            return;
        }
    }
    return;
}
int query(int x)
{
    int nsz=0;
    for(int i = 1; i <= blknum; i++)
    {
        nsz+=v[i].size()-1;
        if(nsz>=l)
        {
            nsz-=v[i].size()-1;
            nsz=l-nsz;
            return v[i][nsz];
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    rn=n;
    sn=n;
    rebuild=20*sqrt(n);
    for(int i = 1; i <= n; i++)
    {
        cin>>b[i];
        a[i]=i;
    }
    build();
    for(int i = 1; i <= sn; i++)
    {
        cin>>op;
        if(op==0)
        {
            cin>>l>>x;
            rn++;
            b[rn]=x;
            add(l,rn);
        }
        else
        {
            cin>>l;
            cout<<b[query(l)]<<'\n';
        }
        rebcnt++;
        if(rebcnt==rebuild)
        {
            expand();
            build();
            rebcnt=0;
        }
    }
    return 0;
}

:::

块状链表的代码留作作业。

数列分块入门 7

猜你想搜：P3373 【模板】线段树 2

维护一个支持区间加，区间乘，区间求和的数组。

n\leq 3\times 10^5

几乎就是和「数列分块入门 4」一样的方法。

但是注意这里在做两端的操作时需要先暴力下放这个块的懒标记，否则会出事（不信的话试试模拟样例，嘿嘿）。

:::success[参考代码 1 935ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[500005],op,l,r,x;
int blksz,blknum,belong[500005],st[5005],ed[5005],sz[5005];
int tag2[5005],tag1[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
        tag1[i]=1;
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++)
    {
        a[i]=(tag1[p]*a[i]+tag2[p])%mod;
    }
    tag1[p]=1;
    tag2[p]=0;
    return;
}
void add1(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++)
        {
            a[i]+=d;
            a[i]%=mod;
        }
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        a[i]+=d;
        a[i]%=mod;
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        tag2[i]+=d;
        tag2[i]%=mod;
    }
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++)
    {
        a[i]+=d;
        a[i]%=mod;
    }
    return;
}
void add2(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++)
        {
            a[i]*=d;
            a[i]%=mod;
        }
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        a[i]*=d;
        a[i]%=mod;
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        tag1[i]*=d;
        tag2[i]*=d;
        tag1[i]%=mod;
        tag2[i]%=mod;
    }
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++)
    {
        a[i]*=d;
        a[i]%=mod;
    }
    return;
}
int query(int l)
{
    return (a[l]*tag1[belong[l]]+tag2[belong[l]])%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add1(l,r,x);
        else if(op==1) add2(l,r,x);
        else cout<<(query(r)+mod)%(mod)<<'\n';
    }
    return 0;
}

:::

怎么又这么慢？

下面是两个针对该代码的优化：

:::success[参考代码 2 784ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[300005],op,l,r,x;
int blksz,blknum,belong[300005],st[5005],ed[5005],sz[5005];
int tag2[5005],tag1[5005];
void build()
{
    blksz=sqrt(n/3.2);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
        tag1[i]=1;
    }
    return;
}
void pushdown(int p)
{
    for(int i = st[p]; i <= ed[p]; i++)
    {
        a[i]=(tag1[p]*a[i]+tag2[p])%mod;
    }
    tag1[p]=1;
    tag2[p]=0;
    return;
}
void add1(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++)
        {
            a[i]+=d;
        }
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        a[i]+=d;
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        tag2[i]+=d;
    }
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++)
    {
        a[i]+=d;
    }
    return;
}
void add2(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++)
        {
            a[i]*=d;
            a[i]%=mod;
        }
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        a[i]*=d;
        a[i]%=mod;
    }
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        tag1[i]*=d;
        tag2[i]*=d;
        tag1[i]%=mod;
        tag2[i]%=mod;
    }
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++)
    {
        a[i]*=d;
        a[i]%=mod;
    }
    return;
}
int query(int l)
{
    return (a[l]*tag1[belong[l]]+tag2[belong[l]])%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>op>>l>>r>>x;
        if(op==0) add1(l,r,x%mod);
        else if(op==1) add2(l,r,x);
        else cout<<(query(r)+mod)%(mod)<<'\n';
    }
    return 0;
}

:::

同时，下面给出了一份由「线段树 2」修改而来的代码，线段树没有倍杀分块，由此可见分块实力之强悍！

:::warning[线段树 583ms]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 10007
struct node
{
    int l,r,add,mul,dat;
};
node t[1200005];
int a[300005],n,m,op,x,y,z,useless;
void pushdown(int p)
{
    if(t[p].mul!=1)
    {
        t[p*2].add*=t[p].mul;
        t[p*2+1].add*=t[p].mul;
        t[p*2].dat*=t[p].mul;
        t[p*2+1].dat*=t[p].mul;
        t[p*2].mul*=t[p].mul;
        t[p*2+1].mul*=t[p].mul;
        t[p*2].add%=mod;
        t[p*2+1].add%=mod;
        t[p*2].dat%=mod;
        t[p*2+1].dat%=mod;
        t[p*2].mul%=mod;
        t[p*2+1].mul%=mod;
        t[p].mul=1;
    }
    if(t[p].add)
    {
        t[p*2].dat+=(t[p*2].r-t[p*2].l+1)*t[p].add;
        t[p*2+1].dat+=(t[p*2+1].r-t[p*2+1].l+1)*t[p].add;
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p*2].dat%=mod;
        t[p*2+1].dat%=mod;
        t[p*2].add%=mod;
        t[p*2+1].add%=mod;
        t[p].add=0;
    }
    return;
}
void pushup(int p)
{
    t[p].dat=(t[p*2].dat+t[p*2+1].dat)%mod;
    return;
}
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    t[p].mul=1;
    if(l==r)
    {
        t[p].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
    return;
}
void update_add(int p,int l,int r,int d)
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].add+=d;
        t[p].dat+=(t[p].r-t[p].l+1)*d;
        t[p].add%=mod;
        t[p].dat%=mod;
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) update_add(p*2,l,r,d);
    if(r>mid) update_add(p*2+1,l,r,d);
    pushup(p);
    return; 
}
void update_mul(int p,int l,int r,int d)
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        t[p].add*=d;
        t[p].mul*=d;
        t[p].dat*=d;
        t[p].add%=mod;
        t[p].mul%=mod;
        t[p].dat%=mod;
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) update_mul(p*2,l,r,d);
    if(r>mid) update_mul(p*2+1,l,r,d);
    pushup(p);
    return; 
}
int query(int p,int l,int r)
{
    if(t[p].l>=l&&t[p].r<=r)
    {
        return t[p].dat;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)/2,res=0;
    if(l<=mid) res+=query(p*2,l,r);
    if(r>mid) res+=query(p*2+1,l,r);
    return res%mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build(1,1,n);
    for(int i = 1; i <= n; i++)
    {
        cin>>op;
        if(op==0)
        {
            cin>>x>>y>>z;
            update_add(1,x,y,z);
        }
        else if(op==1)
        {
            cin>>x>>y>>z;
            update_mul(1,x,y,z);
        }
        else
        {
            cin>>x>>y>>z;
            cout<<(query(1,y,y)%mod+mod)%mod<<'\n';
        }
    }
}

:::

数列分块入门 8

维护一个支持下面操作的数组：

n\leq 3\times 10^5

考虑维护一个懒标记，表示区间是否为同一个数，如果是的话是哪一个数。

在查询整块时，若区间是同一个数，那么直接加即可；若不是，则暴力查询统计。对于散块，pushdown 后暴力查询即可。

同样，修改整块时，对于整块直接修改标记，对于散块暴力修改并修改懒标记即可。

关于时间复杂度：

首先忽略每个块的首次查询，这是 O(n\sqrt{n}) 的。

接下来，对于每个整块：

对于散块，查询修改都是 O(\sqrt{n}) 的，故总复杂度为 O(n\sqrt{n})。

:::success[参考代码 1 717ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[300005],op,l,r,x;
int blksz,blknum,belong[300005],st[5005],ed[5005],sz[5005];
int tag[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
        tag[i]=-1145141919810;
    }
    return;
}
void pushdown(int p)
{
    if(tag[p]==-1145141919810) return;
    for(int i = st[p]; i <= ed[p]; i++) a[i]=tag[p];
    tag[p]=-1145141919810;
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]=d;
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]=d;
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]=d;
    return;
}
int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])
    { 
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) ret+=(a[i]==x);
        return ret;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) ret+=(a[i]==x);
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        if(tag[i]!=-1145141919810) ret+=sz[i]*(tag[i]==x);
        else
        {
            for(int j = st[i]; j <= ed[i]; j++) ret+=(a[j]==x);
        }
    }
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) ret+=(a[i]==x);
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>l>>r>>x;
        cout<<query(l,r,x)<<'\n';
        add(l,r,x);
    }
    return 0;
}

:::

另附推荐块长：B=\sqrt{\frac{n}{2}}。使用这个块长和一些小优化后的代码如下所示。

:::success[参考代码 2 606ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 10007
//#define mod 1000000007
#define int long long
int n,a[300005],op,l,r,x;
int blksz,blknum,belong[300005],st[5005],ed[5005],sz[5005];
int tag[5005];
void build()
{
    blksz=sqrt(n/2);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
        tag[i]=-1145141919810;
    }
    return;
}
void pushdown(int p)
{
    if(tag[p]==-1145141919810) return;
    for(int i = st[p]; i <= ed[p]; i++) a[i]=tag[p];
    tag[p]=-1145141919810;
    return;
}
void add(int l,int r,int d)
{
    if(belong[l]==belong[r])
    {
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) a[i]=d;
        return;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) a[i]=d;
    for(int i = belong[l]+1; i < belong[r]; i++) tag[i]=d;
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) a[i]=d;
    return;
}
int query(int l,int r,int x)
{
    int ret=0;
    if(belong[l]==belong[r])
    { 
        pushdown(belong[l]);
        for(int i = l; i <= r; i++) ret+=(a[i]==x);
        return ret;
    }
    pushdown(belong[l]);
    for(int i = l; i <= ed[belong[l]]; i++) ret+=(a[i]==x);
    for(int i = belong[l]+1; i < belong[r]; i++)
    {
        if(tag[i]!=-1145141919810) ret+=sz[i]*(tag[i]==x);
        else
        {
            for(int j = st[i]; j <= ed[i]; j++) ret+=(a[j]==x);
        }
    }
    pushdown(belong[r]);
    for(int i = st[belong[r]]; i <= r; i++) ret+=(a[i]==x);
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>l>>r>>x;
        cout<<query(l,r,x)<<'\n';
        add(l,r,x);
    }
    return 0;
}

:::

数列分块入门 9

维护一个支持查询区间众数的数组。不带修。

n\leq 3\times 10^5

给出定理：原众数要么是中间整块的众数，要么是两端散块的数。证明如下。

考虑若众数不是中间整块的众数，那么众数必然要利用两端的数进行反超。故这种情况下众数会在两端出现。因此原众数要么是中间整块的众数，要么是两端散块的数。

由于此题不带修，我们可以对块进行一些预处理操作。

整块到整块的众数是容易求出的。这个可以考虑固定左端点，暴力向右扩展来处理。散块的所有数暴力枚举即可。

因此我们现在将候选值的个数缩小到了 2B+1。对于每个数，考虑记录它的所有下标，此时用 lower_bound 和 upper_bound 容易查询 [l,r] 内的出现次数。

注意一定要离散化，预处理带 \log 过不去后果自负。

:::success[参考代码 1 8.24s]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
#define int long long
int n,a[500005],op,l,r,x;
int inv[500005];
map<int,int> mp;
vector<int> pos[500005];
int blksz,blknum,belong[500005];
int st[5005],ed[5005],sz[5005],qmax[5005][5005];
int lstfind[500005],ncnt[500005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
    }
    for(int ns = 1; ns <= blknum; ns++)
    {
        int nmx=n+1;
        for(int i = ns; i <= blknum; i++)
        {
            for(int j = st[i]; j <= ed[i]; j++)
            {
                if(lstfind[a[j]]!=-ns)
                {
                    lstfind[a[j]]=-ns;
                    ncnt[a[j]]=0;
                }
                ncnt[a[j]]++;
                if(ncnt[a[j]]>ncnt[nmx]||(ncnt[a[j]]==ncnt[nmx]&&a[j]<nmx)) nmx=a[j];
            }
            qmax[ns][i]=nmx;
        }
    }
    return;
}
int query(int l,int r,int nid)
{
    int ret=-1,retc=-1,nnow;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++)
        {
            if(lstfind[a[i]]==nid) continue;
            lstfind[a[i]]=nid;
            nnow=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l);
            if(nnow>retc||(nnow==retc&&a[i]<ret))
            {
                ret=a[i];
                retc=nnow;
            }
        }
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        if(lstfind[a[i]]==nid) continue;
        lstfind[a[i]]=nid;
        nnow=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l);
        if(nnow>retc||(nnow==retc&&a[i]<ret))
        {
            ret=a[i];
            retc=nnow;
        }
    }
    if(belong[l]+1!=belong[r]&&lstfind[qmax[belong[l]+1][belong[r]-1]]!=nid)
    {
        lstfind[qmax[belong[l]+1][belong[r]-1]]=nid;
        nnow=upper_bound(pos[qmax[belong[l]+1][belong[r]-1]].begin(),pos[qmax[belong[l]+1][belong[r]-1]].end(),r)-lower_bound(pos[qmax[belong[l]+1][belong[r]-1]].begin(),pos[qmax[belong[l]+1][belong[r]-1]].end(),l);
        if(nnow>retc||(nnow==retc&&qmax[belong[l]+1][belong[r]-1]<ret))
        {
            ret=qmax[belong[l]+1][belong[r]-1];
            retc=nnow;
        }
    }
    for(int i = st[belong[r]]; i <= r; i++)
    {
        if(lstfind[a[i]]==nid) continue;
        lstfind[a[i]]=nid;
        nnow=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l);
        if(nnow>retc||(nnow==retc&&a[i]<ret))
        {
            ret=a[i];
            retc=nnow;
        }
    }
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        mp[a[i]]=1;
    }
    int ncnt=0;
    for(auto it = mp.begin(); it != mp.end(); it++)
    {
        ncnt++;
        it->second=ncnt;
        inv[ncnt]=it->first;
    }
    for(int i = 1; i <= n; i++) pos[i].push_back(0);
    for(int i = 1; i <= n; i++)
    {
        a[i]=mp[a[i]];
        pos[a[i]].push_back(i);
    }
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>l>>r;
        cout<<inv[query(l,r,i)]<<'\n';
    }
    return 0;
}

:::

怎么又这么慢？

不妨分析一下复杂度：

合起来总复杂度 O(\frac{n^2}{B}+nB\log B)，在 B=\sqrt{\frac{n}{\log n}} 时取到最小值 O(n\sqrt{n\log n})。

同时 #define int long long 是没必要的，这题可以不开，能优化一点时间。

:::success[参考代码 2 4.26s]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
// #define int long long
int n,a[300005],op,l,r,x;
int inv[300005];
map<int,int> mp;
vector<int> pos[300005];
int blksz,blknum,belong[300005];
int st[3005],ed[3005],sz[3005],qmax[3005][3005];
int lstfind[300005],ncnt[300005];
void build()
{
    blksz=sqrt(n/log2(n));
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
    }
    for(int ns = 1; ns <= blknum; ns++)
    {
        int nmx=n+1;
        for(int i = ns; i <= blknum; i++)
        {
            for(int j = st[i]; j <= ed[i]; j++)
            {
                if(lstfind[a[j]]!=-ns)
                {
                    lstfind[a[j]]=-ns;
                    ncnt[a[j]]=0;
                }
                ncnt[a[j]]++;
                if(ncnt[a[j]]>ncnt[nmx]||(ncnt[a[j]]==ncnt[nmx]&&a[j]<nmx)) nmx=a[j];
            }
            qmax[ns][i]=nmx;
        }
    }
    return;
}
int query(int l,int r,int nid)
{
    int ret=-1,retc=-1,nnow;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++)
        {
            if(lstfind[a[i]]==nid) continue;
            lstfind[a[i]]=nid;
            nnow=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l);
            if(nnow>retc||(nnow==retc&&a[i]<ret))
            {
                ret=a[i];
                retc=nnow;
            }
        }
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        if(lstfind[a[i]]==nid) continue;
        lstfind[a[i]]=nid;
        nnow=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l);
        if(nnow>retc||(nnow==retc&&a[i]<ret))
        {
            ret=a[i];
            retc=nnow;
        }
    }
    if(belong[l]+1!=belong[r]&&lstfind[qmax[belong[l]+1][belong[r]-1]]!=nid)
    {
        lstfind[qmax[belong[l]+1][belong[r]-1]]=nid;
        nnow=upper_bound(pos[qmax[belong[l]+1][belong[r]-1]].begin(),pos[qmax[belong[l]+1][belong[r]-1]].end(),r)-lower_bound(pos[qmax[belong[l]+1][belong[r]-1]].begin(),pos[qmax[belong[l]+1][belong[r]-1]].end(),l);
        if(nnow>retc||(nnow==retc&&qmax[belong[l]+1][belong[r]-1]<ret))
        {
            ret=qmax[belong[l]+1][belong[r]-1];
            retc=nnow;
        }
    }
    for(int i = st[belong[r]]; i <= r; i++)
    {
        if(lstfind[a[i]]==nid) continue;
        lstfind[a[i]]=nid;
        nnow=upper_bound(pos[a[i]].begin(),pos[a[i]].end(),r)-lower_bound(pos[a[i]].begin(),pos[a[i]].end(),l);
        if(nnow>retc||(nnow==retc&&a[i]<ret))
        {
            ret=a[i];
            retc=nnow;
        }
    }
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        mp[a[i]]=1;
    }
    int ncnt=0;
    for(auto it = mp.begin(); it != mp.end(); it++)
    {
        ncnt++;
        it->second=ncnt;
        inv[ncnt]=it->first;
    }
    for(int i = 1; i <= n; i++) pos[i].push_back(0);
    for(int i = 1; i <= n; i++)
    {
        a[i]=mp[a[i]];
        pos[a[i]].push_back(i);
    }
    build();
    for(int i = 1; i <= n; i++)
    {
        cin>>l>>r;
        cout<<inv[query(l,r,i)]<<'\n';
    }
    return 0;
}

:::

AT_aalc001_a セグメント木

维护一个支持单点修改，区间求 \min 的数组。

n\leq 2\times 10^5

模仿「数列分块入门 4」的思路。

每一块维护一个块内所有元素的 \min，单点修改就重建这个块的 \min，区间求 \min 把这个区间每个块和散块的所有元素求 \min 即可。

:::success[参考代码 136ms]

#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
//#define int long long
int n,m,a[200005],op,l,r,x;
int blksz,blknum,belong[200005],nmin[5005],st[5005],ed[5005],sz[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        nmin[i]=1145141919;
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            nmin[i]=min(nmin[i],a[j]);
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
void update(int l,int d)
{
    a[l]=d;
    nmin[belong[l]]=1145141919;
    for(int i = st[belong[l]]; i <= ed[belong[l]]; i++) nmin[belong[l]]=min(nmin[belong[l]],a[i]);
    return;
}
int query(int l,int r)
{
    int ret=1145141919;
    if(belong[l]==belong[r])
    {
        for(int i = l; i <= r; i++) ret=min(ret,a[i]);
        return ret;
    }
    for(int i = l; i <= ed[belong[l]]; i++) ret=min(ret,a[i]);
    for(int i = belong[l]+1; i < belong[r]; i++) ret=min(ret,nmin[i]);
    for(int i = st[belong[r]]; i <= r; i++) ret=min(ret,a[i]);
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= m; i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>l>>x;
            update(l,x);
        }
        else
        {
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }
    }
    return 0;
}

:::

甚至可以打败一些实现较差的线段树。

AT_aalc001_c セグメント木上の二分探索

保证任意时刻元素非负，维护一个支持单点修改和下面两种查询的数组：

n\leq 2\times 10^5

对于每个块，我们维护块内所有元素的和。

对于查询，考虑一个暴力的过程：

不难发现，记块长为 B，这个暴力查找的复杂度为 O(B+\frac{n}{B}) 的，在 B=\sqrt{n} 时有最优复杂度 O(\sqrt{n})。

至于单点改，直接修改这个数并更新块内和就完事了。

甚至比很多线段树跑得快！

:::success[参考代码 91ms]


#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
#define mod 998244353
//#define mod 1000000007
#define int long long
int n,m,a[200005],op,l,r,x;
int blksz,blknum,belong[200005];
int tag[5005],sum[5005],st[5005],ed[5005],sz[5005];
void build()
{
    blksz=sqrt(n);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
            sum[i]+=a[j];
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
void add(int l,int d)
{
    sum[belong[l]]-=a[l];
    a[l]=d;
    sum[belong[l]]+=a[l];
    return;
}
int queryl(int l,int x)
{
    int ret=0;
    for(int i = l; i <= ed[belong[l]]; i++)
    {
        ret+=a[i];
        if(ret>=x) return i;
    }
    for(int i = belong[l]+1; i <= blknum; i++)
    {
        ret+=sum[i];
        if(ret>=x)
        {
            ret-=sum[i];
            for(int j = st[i]; j <= ed[i]; j++)
            {
                ret+=a[j];
                if(ret>=x) return j;
            }
        }
    }
    return n+1;
}
int queryr(int r,int x)
{
    int ret=0;
    for(int i = r; i >= st[belong[r]]; i--)
    {
        ret+=a[i];
        if(ret>=x) return i;
    }
    for(int i = belong[r]-1; i >= 1; i--)
    {
        ret+=sum[i];
        if(ret>=x)
        {
            ret-=sum[i];
            for(int j = ed[i]; j >= st[i]; j--)
            {
                ret+=a[j];
                if(ret>=x) return j;
            }
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build();
    for(int i = 1; i <= m; i++)
    {
        cin>>op>>l>>x;
        if(op==1) add(l,x);
        else if(op==2) cout<<queryl(l,x)<<'\n';
        else cout<<queryr(l,x)<<'\n';
    }
    return 0;
}
:::