分块（一）

2022 年 11 月 10 日
筆記

分块（一）

优雅的暴力~~

一、一些题目

基本思想：

将原序列划分成 \(\sqrt n\) 个块，记录每一个元素对应其所在块的编号，统计每个块的信息。

（至于为什么是 \(\sqrt n\)，下面会讲到~~）

这里，我们用 \(id\) 表示每个元素对应块的编号，每一块的长度为 \(len\)，具体如下：

当 \(i\in[1,len]\) 时，\(id[i]=1\)；

当 \(i\in[len+1,2\times len]\) 时，\(id[i]=2\)；

……

当 \(i\in[(len-1)\times len+1,n]\) 时，\(id[i]=n/len+1\)。

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1; 
}

Tips: 关于 \(id[i]\) 的计算

i-1 是为了保证第一个块有 \(len\) 个元素，而不是 \(len-1\) 个；
+1 是为了让第一个块的编号为 \(1\)，而不是 \(0\)。

对于每一个区间操作，分为如下两种情况：

左右端点在同一个块中，枚举整个区间暴力求解
左右端点在不同的块中：

① 对于能完全包含在内的块，我们称为完整块，直接利用这个块预处理的信息，\(O(1)\) 得到答案；

② 对于区间两端不能涵盖的整块，我们称为不完整块，暴力枚举求解即可。

两个操作的时间复杂度最优为 \(O(\sqrt n)\)。

有一张图，或许能帮助你理解：

关于 \(\sqrt n\) 的小证明：

需要一点高中数学知识：~~（真的只有一点，不是亿点）~~

基本不等式：\(\cfrac {a+b} 2 \geq \sqrt {ab}\)，当且仅当 \(a=b\) 时，等号成立。

左右端点在同一个块中，暴力枚举整个块，复杂度最坏为 \(O(len)\)；
左右端点不在同一个块中，答案由三部分组成：以 \(l\) 开偷的不完整块、中间几个完整块、以 \(r\) 结尾的不完整块。

① 对于完整块，时间复杂度为 \(O(\cfrac n {len})\)；

② 对于不完整块，时间复杂度为 \(O(len)\)

故最坏复杂度的和为 \(O(\cfrac n {len} + len)\)，由基本不等式可得：

\(\cfrac n {len} + len \geq 2\sqrt{\cfrac n {len} \times len} = 2 \sqrt n\)，当且仅当 \(\cfrac n {len} = len\)，即 \(len=\sqrt n\) 时，等号成立。

也就是单次操作的时间复杂最优，为 \(O(\sqrt n)\)，此时块长也为 \(\sqrt n\)。

既然基本思想已经知道了，那就来 “亿”点点 例题实践一下吧：

Example1: 数列分块入门1 LibreOJ #6277

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，单点查值。

区间增加

我们可以对于每一个块，按照分块的基本思想进行累加即可：

对于 完整块，利用数组 \(b\) 存储对于块整体加的值，不必对于每一个 \(a[i]\) 做加法；
对于 不完整块 或 左右端点在同一个块中，暴力枚举，对 \(a[i]\) 做加法即可。

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r]; // 左右两端点对于块的编号
    if(lid==rid) // 左右端点在同一个块中
    {
        for(int i=l;i<=r;i++) // 暴力加
            a[i]+=v;
        return;
    }
    for(int i=l;id[i]==lid;i++) // 以l开头的不完整块，暴力加
        a[i]+=v;
    for(int i=lid+1;i<rid;i++) // 完整块，直接改变b的值
        b[i]+=v;
    for(int i=r;id[i]==rid;i--) // 以r结尾的不完整块，暴力加
        a[i]+=v;
}

Tips:

对于完整块的操作，for 中的 \(i\) 表示块的编号，而不是元素的编号；
若 \(a\) 的下标为 \(i\)，则 \(b\) 的下标为 \(id[i]\)。

单点查询

直接输出本身的值 \(a[i]\) 与该元素所在块的 \(b[id[i]]\)。

int ask(int l,int r)
{
	return a[r]+b[id[r]];
}

Example2: 数列分块入门2 LibreOJ #6278

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，询问区间内小于某个值 \(x\) 的元素个数。

相较于上一题，多了区间查询。

区间查询

看到 小于 \(x\) 的个数，直接想到二分

这道题中，我们可以 用 vector 存储每一个块所有元素的值，方便进行二分查找。

对于 完整块，二分对应块的全部元素，统计个数；
对于 不完整块 或 左右端点在同一个块中，暴力枚举，统计 \(a[i]<v\) 的个数。

int clac(int x,int v) // 手写二分需要此函数
{
    int l=0,r=vec[x].size();
    while(l+1<r)
    {
        int mid=l+r>>1;
        if(vec[x][mid]+b[x]<v) l=mid; // 别忘记加b数组的值
        else r=mid;
    }
    if(vec[x][l]+b[x]<v) return l+1; //vector从0开始存储，数组从1开始存储，+1保证下标对应
    else if(vec[x][r]+b[x]<v) return r+1;
    else return 0;  
}

int ask(int l,int r,int v)
{
    int lid=id[l],rid=id[r],res=0;
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            if(a[i]+b[id[i]]<v) res++;
        return res;
    }
    for(int i=l;id[i]==lid;i++)
        if(a[i]+b[id[i]]<v) res++;
    for(int i=lid+1;i<rid;i++)
        res+=clac(i,v); // 手写二分，下面为STL
//      res+=lower_bound(vec[i].begin(),vec[i].end(),v-b[i])-vec[i].begin();
    for(int i=r;id[i]==rid;i--)
        if(a[i]+b[id[i]]<v) res++;
    return res;
}

区间增加

由于块用 vector 存了起来，所以每一次按照正常单点增加的造作之后，更新一下对应 vector。

void change(int x)
{
    vec[x].clear();
    int l=(x-1)*len+1,r=min(x*len,n);
    for(int i=l;i<=r;i++)
        vec[x].push_back(a[i]);
    sort(vec[x].begin(),vec[x].end());
}

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        a[i]+=v;
        change(lid); 
        return;
    }
    
    for(int i=l;id[i]==lid;i++)
    a[i]+=v;
    change(lid);
    
    for(int i=lid+1;i<rid;i++)
        b[i]+=v;
    
    for(int i=r;id[i]==rid;i--)
        a[i]+=v;
    change(rid);
}

初始化

其实也没有什么变化，多存一个 vector 即可。

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1;
    vec[id[i]].push_back(a[i]);
}

Example3: 数列分块入门3 LibreOJ #6279

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，询问区间内小于某个值 \(x\) 的前驱（比其小的最大元素）。

区间增加和上题一样，区间查询的时候，将二分答案的返回值更改为当前元素的值即可。

int get(int x,int v)
{
    int l=0,r=vec[x].size();
    while(l+1<r)
    {
        int mid=l+r>>1;
        if(vec[x][mid]+b[x]<v) l=mid;
        else r=mid;
    }
    if(vec[x][l]+b[x]<v) return vec[x][l]+b[x];
    else if(vec[x][r]+b[x]<v) return vec[x][r]+b[x];
    else return -1; // 当前块中没有<v的数，返回-1
}

int ask(int l,int r,int v)
{
    int lid=id[l],rid=id[r],ans=-1;
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            if(a[i]+b[lid]<v) ans=max(ans,a[i]+b[lid]);
        return ans;
    } 
    for(int i=l;id[i]==lid;i++)
        if(a[i]+b[lid]<v) ans=max(ans,a[i]+b[lid]);
    for(int i=lid+1;i<rid;i++)
        ans=max(ans,get(i,v));
    for(int i=r;id[i]==rid;i--)
        if(a[i]+b[rid]<v) ans=max(ans,a[i]+b[rid]);
    return ans; 
}

Example4: 数列分块入门4 LibreOJ #6280

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及区间加法，区间求和。

在这道题中，我们再引用一个 数组 \(s\) ，\(s[i]\) 表示第 \(i\) 个块的数值和。

因此在预处理的时候，需要更新一下数组 \(s\)：

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1;
    s[id[i]]+=a[i];
}

区间增加

注意在增加的时候及时更改数组 \(s\) 的值。

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        a[i]+=v,s[lid]+=v;
        return;
    } 
    for(int i=l;id[i]==lid;i++)
    a[i]+=v,s[lid]+=v;
    for(int i=lid+1;i<rid;i++)
        b[i]+=v,s[i]+=(LL)v*len; // 一个块有len个元素，每个元素增加v。共增加v*len
    for(int i=r;id[i]==rid;i--)
        a[i]+=v,s[rid]+=v;
}

区间求和

对于 完整块，直接返回数组 \(s\) 的值即可；
对于 不完整块 或 左右端点在同一个块中，暴力枚举每一个点，累加每一个点的值。

LL ask(int l,int r,int p)
{
    LL res=0;
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            res=(LL)(res+a[i]+b[lid])%p;
        return res;
    }
    for(int i=l;id[i]==lid;i++)
        res=(LL)(res+a[i]+b[lid])%p;
    for(int i=lid+1;i<rid;i++)
        res=(LL)(res+s[i])%p;
    for(int i=r;id[i]==rid;i--)
        res=(LL)(res+a[i]+b[rid])%p;
    return res;
}

Example5: 数列分块入门5 LibreOJ #6281

给出一个长为 \(n\) 的数列 \(a_1 ,\ldots, a_n\)，以及 \(n\) 个操作，操作涉及区间开方，区间求和。

区间开方

我们知道，开方操作能使数值快速减小。

故可以引用 数组 \(tag\) 用来标记每一个块的所有元素是否全部变为 \(1\)，

如果全都变为 \(1\) 了，之后再进行开方操作就可以跳过，优化时间复杂度。

由于本题仍需区间求和，开方的时候不方便直接更改数组 \(s\) 的值，

因此我们可以在更改 \(a[i]\) 的时候，先减去 \(a[i]\)，再将开方过后的值加到数组\(s\) 中。

void change(int l,int r)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        {
            if(tag[lid]) break; // 该块全部为1.开方操作没有任何作用，直接跳过
            s[lid]-=a[i]; // 先减去原本元素的值
            a[i]=sqrt(a[i]);
            s[lid]+=a[i]; // 加上开方之后该元素的值
        }
        return;
    }
    for(int i=l;id[i]==lid;i++)
    {
        if(tag[lid]) break;
        s[lid]-=a[i];
        a[i]=sqrt(a[i]);
        s[lid]+=a[i];
    }
    for(int i=lid+1;i<rid;i++)
    {
        if(tag[i]) continue; // 注意这里不能break！！！
        tag[i]=true; s[i]=0;
        for(int j=(i-1)*len+1;j<=min(i*len,n);j++)
        {
            a[j]=sqrt(a[j]);
            s[i]+=a[j];
            if(a[j]>1) tag[i]=false; // 有一个元素>1，就为false；只有全部为1的时候，才是true
        }
    }
    for(int i=r;id[i]==rid;i--)
    {
        if(tag[rid]) break;
        s[rid]-=a[i];
        a[i]=sqrt(a[i]);
        s[rid]+=a[i];
    }
}

区间求和

由于没有增加操作，也就不必统计数组 \(b\)。

int ask(int l,int r)
{
    int lid=id[l],rid=id[r],res=0;
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
            res+=a[i];
        return res;
    }
    for(int i=l;id[i]==lid;i++)
        res+=a[i];
    for(int i=lid+1;i<rid;i++)
        res+=s[i];
    for(int i=r;id[i]==rid;i--)
        res+=a[i];
    return res; 
}

Example6: 数列分块入门6 LibreOJ #6282

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及单点插入，单点询问，数据随机生成。

单点插入

对于单点插入，显然之前用的分块方法不太可行了。

这时，我们可以利用 vector 可以插入元素的特性，将每一个块都存到一个堆中。

对于每一个插入操作，找到插入位置对应的块以及在块中的位置即可。

typedef pair<int,int> PII;

PII get(int x) // 找到插入位置对应的块以及位置
{
    int cnt=0,i; // cnt表示前面的块共有多少个元素，i表示此时在第几个块
    for(i=1;cnt+vec[i].size()<x;i++) // 只要这个块仍然到达不了位置x
        cnt+=vec[i].size(); // 加上这个块的长度
    return {i,x-cnt}; // x-cnt就是位置x，是第i个块的第几个元素
}

void add(int x,int v)
{
    PII t=get(x);
    vec[t.first].insert(vec[t.first].begin()+t.second-1,v); 
    // 由于要在x前面增加新元素v，故要-1
}

单点查询

有了插入的基础，查询就非常容易了。

还是利用 \(get\) 函数找到对应的块以及在块中的位置即可。

int ask(int x)
{
    PII t=get(x);
    return vec[t.first][t.second-1];
}

初始化

由于块都存到了 vector 中，就不需要数组 \(id\) 记录每一个元素对应块的编号了。

scanf("%d",&n);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
    int x,y;
    scanf("%d",&x);
    y=(i-1)/len+1;
    vec[y].push_back(x);
}

Example7: 数列分块入门7 LibreOJ #6283

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间乘法，区间加法，单点询问。

利用 线段树延迟标记 的思想~~（既然都学分块了，就一定会线段树吧(～￣▽￣)～）~~

用 \(add\_tag[i]\) 表示第 \(i\) 个块整体增加的值，\(mul\_tag[i]\) 表示第 \(i\) 个块整体乘的值

每次对 不完整块 进行处理时，将标记下传给元素本身，在进行操作即可。

由于加法和乘法混合进行，为了保证下传标记次数不变，

我们可以让每一次进行乘法操作时，同时将 \(add\_tag\) 的值也进行乘法运算。

void spread(int x)
{
    int l=(x-1)*len+1,r=min(x*len,n);
    for(int i=l;i<=r;i++)
        a[i]=Add(Pow(a[i],mul_tag[x]),add_tag[x]);
        // 每次乘法进行处理之后，返回给元素的值就要先乘后加了，因为加的值以及乘过了
    
    // 下传操作完成之后，清空所有标记数组
    add_tag[x]=0; // 加法初值为0
    mul_tag[x]=1; // 乘法初值为1
}

Tips: Add 与 Pow 函数：在函数中进行 \(\bmod\) 运算，防止代码中部分运算忘记 \(\bmod\)，导致最终结果错误。

inline int Add(int a,int b)
{
    return a+b>=Mod?a+b-Mod:a+b;
}

inline int Pow(int a,int b)
{
    return (LL)a*b%Mod;
}

区间加法

void add(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        spread(lid);
        for(int i=l;i<=r;i++)
            a[i]=Add(a[i],v);
        return; 
    }
    
    spread(lid);
    for(int i=l;id[i]==lid;i++)
        a[i]=Add(a[i],v);
    
    for(int i=lid+1;i<rid;i++)
        add_tag[i]=Add(add_tag[i],v);
    
    spread(rid);
    for(int i=r;id[i]==rid;i--)
        a[i]=Add(a[i],v);
}

区间乘法

void mul(int l,int r,int v)
{
    int lid=id[l],rid=id[r];
    if(lid==rid)
    {
        spread(lid);
        for(int i=l;i<=r;i++)
            a[i]=Pow(a[i],v);
        return; 
    }
    
    spread(lid);
    for(int i=l;id[i]==lid;i++)
        a[i]=Pow(a[i],v);
    
    for(int i=lid+1;i<rid;i++)
    {
        mul_tag[i]=Pow(mul_tag[i],v);
        add_tag[i]=Pow(add_tag[i],v); // 不要忘了同时更新add_tag的值
    }
    
    spread(rid);
    for(int i=r;id[i]==rid;i--)
        a[i]=Pow(a[i],v);
}

单点查询

要先下传标记哦，否则结果会错误。

int ask(int x)
{
    spread(id[x]);
    return a[x]; 
}

Tips: 别忘了把 \(mul\_tag\) 的值都设为 \(1\)。

for(int i=1;i<=id[n];i++) // 用id[n]，而不是len，有可能有1的误差
    mul_tag[i]=1;

Example8: 数列分块入门8 LibreOJ #6284

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，

操作涉及区间询问等于一个数 \(c\) 的元素，并将这个区间的所有元素改为 \(c\)。

如果一个块中所有的元素都为同一个值，就不必再遍历每一个数了。

利用上述思想进行优化分块即可。

用 \(tag[i]\) 表示第 \(i\) 个块元素的值是否都一样，\(b[i]\) 表示第 \(i\) 块集体更改的值。

void spread(int x)
{
    if(tag[x]) // 如果这个块元素的值都一样，将每个元素的值更新一下
    {
        int l=(x-1)*len+1,r=min(x*len,n);
        for(int i=l;i<=r;i++)
            a[i]=b[x];
    }
}

int solve(int l,int r,int v)
{
    int lid=id[l],rid=id[r],cnt=0;
    if(lid==rid)
    {
        spread(lid); // 下传这个块的值
        for(int i=l;i<=r;i++)
        {
            if(a[i]==v) cnt++; // 如果值为v，统计个数+1
            else a[i]=v; // 否则将这个元素的值改为v
        }
        tag[lid]=false; // 这个块的元素值不同了，因为只有一部分元素的值进行多了更改
        return cnt;
    }
    
    spread(lid);
    for(int i=l;id[i]==lid;i++)
    {
        if(a[i]==v) cnt++;
        else a[i]=v;
    }
    tag[lid]=false;
    
    for(int i=lid+1;i<rid;i++)
    {
        if(tag[i]) // 如果这个块的元素值相同
        {
            if(b[i]==v) cnt+=sze[i]; // 如果这个块的值为v，答案加上这个块的长度
                else b[i]=v; // 否则这个块的值改为v
        }
        else // 元素值不同只能进行暴力更改
        {
            int ll=(i-1)*len+1,rr=min(i*len,n);
            for(int j=ll;j<=rr;j++)
                if(a[j]==v) cnt++;
            // 查询之后这个块的值就统一更改为v了，更新标记
            tag[i]=true; 
            b[i]=v;
        }
    }
    
    spread(rid);
    for(int i=r;id[i]==rid;i--)
    {
        if(a[i]==v) cnt++;
        else a[i]=v;
    }
    tag[rid]=false;
    
    return cnt;
}

Tips: 用数组 \(sze\) 表示每一个块的长度，调用更方便。

for(int i=1;i<=id[n];i++)
{
    int l=(i-1)*len+1,r=min(i*len,n);
    sze[i]=r-l+1; // 由于最后一个块不一定为整块，故不能直接等于块长len
}

Example9: 数列分块入门9 LibreOJ #6285

给出一个长为 \(n\) 的数列，以及 \(n\) 个操作，操作涉及询问区间的最小众数。

最后一道例题了，开心吗(oﾟvﾟ)ノ~~（这是最难的一道例题了）~~

由于不会进行更改元素的值，我们可以预处理出每一块的区间众数，与分块思想照应。

这里我们用 pair<int,int> 来存储数组 \(f\)。

\(f[i][j].first\) 表示 \(i\sim j\) 的块中，出现次数最多的的值，次数为多少。

\(f[i][j].second\) 表示 \(i\sim j\) 的块中，出现次数最多的值，最小为多少。（因为询问最小众数）

for(int i=1;i<=id[n];i++)
{
    int max_cnt=0,min_val=0,cnt[N];
    memset(cnt,0,sizeof cnt); // 记得清空cnt

    int l=(i-1)*len+1;
    for(int j=l;j<=n;j++) // 要一直枚举到n哦~
    {
        cnt[a[j]]++;
        if(max_cnt<cnt[a[j]] || (max_cnt==cnt[a[j]]&&min_val>a[j]))
        // 找到出现次数最多的，值最小的那个数
            max_cnt=cnt[a[j]],min_val=a[j];
        f[i][id[j]]={max_cnt,min_val};
    } 
}

因为本题元素值较大，不能作为数组下标，需要离散化。

scanf("%d",&n);
len=80; // len=sqrt(n) 会超时，不清楚为什么 ＞︿＜
for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    id[i]=(i-1)/len+1;
    c[i]=a[i]; // 用c[i]进行离散化
}

// STL离散化
sort(c+1,c+1+n);
int cn=unique(c+1,c+1+n)-(c+1);

for(int i=1;i<=n;i++)
{
    int t=lower_bound(c+1,c+1+cn,a[i])-(c+1);
    // 在c中找到第一个大于等于a[i]的位置
    // 由于c中元素值和a中是相同的，也就是找到离散化之后a[i]的位置
    b[t]=a[i]; // b[a[i]]的值为没有离散化时a[i]的值
    a[i]=t; // 离散化之后第i个数的位置，也就是离散化之后的值
    vec[a[i]].push_back(i); // 用vec存值为a[i]元素的位置
}

之后进行分块处理就行了。

int solve(int l,int r)
{
    int lid=id[l],rid=id[r];
    // 直接统计整块的信息
    int max_cnt=f[lid+1][rid-1].first;
    int min_val=f[lid+1][rid-1].second;
    
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        {
            auto& t=vec[a[i]];
            int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
            // 找到>r的位置和>=l的位置，两者相减就是l~r中值为a[i]的个数
            if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
                max_cnt=cnt,min_val=a[i];
        }
        return min_val;
    }
    
    for(int i=l;id[i]==lid;i++)
    {
        auto& t=vec[a[i]];
        int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
        if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
            max_cnt=cnt,min_val=a[i];
    }
    
    for(int i=r;id[i]==rid;i--)
    {
        auto& t=vec[a[i]];
        int cnt=upper_bound(t.begin(),t.end(),r)-lower_bound(t.begin(),t.end(),l);
        if(max_cnt<cnt || (max_cnt==cnt&&min_val>a[i]))
            max_cnt=cnt,min_val=a[i];
    }
    
    return min_val;
}

在最后输出的时候，应输出原数值，而不是离散化之后的。

for(int i=1;i<=n;i++)
{
    int l,r;
    scanf("%d%d",&l,&r);
    printf("%d\n",b[solve(l,r)]);
}

Exercise1: 蒲公英 Luogu P4168 [Violet]

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为 \(n\) 的序列 \(\{a_1,a_2..a_n\}\)，

其中 \(a_i\) 为一个正整数，表示第 \(i\) 棵蒲公英的种类编号。

而每次询问一个区间 \([l, r]\)，你需要回答区间里出现次数最多的是哪种蒲公英，

如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的。

简化题意：和 Example9 一模一样。

在输出的时候根据输出要求进行在线操作即可。

int x=0;
for(int i=1;i<=m;i++)
{
    int l,r;
    scanf("%d%d",&l,&r);
    l=(l+x-1)%n+1,r=(r+x-1)%n+1;
    if(l>r) swap(l,r);
    int ans=solve(l,r);
    printf("%d\n",b[ans]);
    x=b[ans];
}

Exercise2: 作诗 Luogu P4315

SHY 找来一篇长度为 \(n\) 的文章，阅读 \(m\) 次，

每次只阅读其中连续的一段 \([l,r]\)，从这一段中选出一些汉字构成诗。

因为 SHY 喜欢对偶，所以 SHY 规定最后选出的每个汉字都必须在 \([l,r]\) 里出现了正偶数次。

而且 SHY 认为选出的汉字的种类数越多越好。

问题简述：

给定 \(n\) 个不大于 \(c\) 的正整数 \(a_1 \dots a_n\) 和 \(m\) 组询问，每次问 \([l,r]\) 中有多少个数出现正偶数次。

不难发现，和上题的题型非常相似，因此只是统计内容变了。

因此我们根据题意，更改一下 \(f\) 数组的含义即可。

\(sum[i][j]\) 表示前 \(i\) 个块中汉字为 \(j\) 的个数。

\(cnt[i][j]\) 表示 \(i\sim j\) 的块中，根据题意的结果为多少。

for(int i=2;i<=id[n];i++)
    for(int j=1;j<=c;j++)
        sum[i][j]+=sum[i-1][j];

for(int i=1;i<=id[n];i++)
{
    int res=0,l=(i-1)*len+1;
    for(int j=l;j<=n;j++)
    {
        cnt[a[j]]++;
        if(cnt[a[j]]%2==0 && cnt[a[j]]) res++; // 为偶数，数量+1
        else if(cnt[a[j]]>2) res--; // 由偶数又变成了奇数，数量-1
        f[i][id[j]]=res;
    }
    
    // 清空cnt数组
    for(int j=l;j<=n;j++)
        cnt[a[j]]--;
}

之后和上题一样按照分块的思想进行处理即可。

int solve(int l,int r)
{
    int lid=id[l],rid=id[r];
    int res=f[lid+1][rid-1];
    
    if(lid==rid)
    {
        for(int i=l;i<=r;i++)
        {
            cnt[a[i]]++;
            if(cnt[a[i]]%2==0 && cnt[a[i]]) res++;
            else if(cnt[a[i]]>2) res--; 
        }
        
        for(int i=l;i<=r;i++)
            cnt[a[i]]--;
        return res;
    } 
    
    for(int i=l;id[i]==lid;i++)
    {
        cnt[a[i]]++;
        int t=cnt[a[i]]+sum[rid-1][a[i]]-sum[lid][a[i]];
        // 记得加上 lid+1~rid-1 之间的块中相同汉字的数量
        // 为了后续清空数组耗时短，不再累加到cnt数组中
        if(t%2==0 && t) res++;
        else if(t>2) res--;
    }
    
    for(int i=r;id[i]==rid;i--)
    {
        cnt[a[i]]++;
        int t=cnt[a[i]]+sum[rid-1][a[i]]-sum[lid][a[i]];
        if(t%2==0 && t) res++;
        else if(t>2) res--;
    }
    
    for(int i=l;id[i]==lid;i++)
        cnt[a[i]]--;
    for(int i=r;id[i]==rid;i--)
        cnt[a[i]]--;
    return res;
}

二、一些想法

分块的各种操作不像树状数组或者线段树那样，基本操作的写法不变

它会根据查询内容的不同写法发生很大变化，同时 vector 似乎发挥了很大作用
还有一些题，先不写了，这些基本的板子题先写出来，然后去写莫队啦༼ つ ◕_◕ ༽つ

其他题有时间了再写，到时候再写下一个分块的博客吧
这篇博客只写了半天，和上篇单调队列相比，时间少了好多

可能是这篇是题都写完了才写的博客，上一个是一边学一边写

也可能是越写越快吧(o゜▽゜)o☆

分块（一）

分块（一）

一、一些题目

基本思想：

关于 \(\sqrt n\) 的小证明：

Example1: 数列分块入门1 LibreOJ #6277

Example2: 数列分块入门2 LibreOJ #6278

Example3: 数列分块入门3 LibreOJ #6279

Example4: 数列分块入门4 LibreOJ #6280

Example5: 数列分块入门5 LibreOJ #6281

Example6: 数列分块入门6 LibreOJ #6282

Example7: 数列分块入门7 LibreOJ #6283

Example8: 数列分块入门8 LibreOJ #6284

Example9: 数列分块入门9 LibreOJ #6285

Exercise1: 蒲公英 Luogu P4168 [Violet]

Exercise2: 作诗 Luogu P4315

二、一些想法

VirMach 便宜 VPS

QNews

分块（一）

分块（一）

一、一些题目

基本思想：

关于 \(\sqrt n\) 的小证明：

Example1: 数列分块入门1 LibreOJ #6277

Example2: 数列分块入门2 LibreOJ #6278

Example3: 数列分块入门3 LibreOJ #6279

Example4: 数列分块入门4 LibreOJ #6280

Example5: 数列分块入门5 LibreOJ #6281

Example6: 数列分块入门6 LibreOJ #6282

Example7: 数列分块入门7 LibreOJ #6283

Example8: 数列分块入门8 LibreOJ #6284

Example9: 数列分块入门9 LibreOJ #6285

Exercise1: 蒲公英 Luogu P4168 [Violet]

Exercise2: 作诗 Luogu P4315

二、一些想法

分享此文：

Related Posts

原来MySQL面试还会问这些…

测试开发【提测平台】分享5-实现产品线的添加

词向量word2vec（图学习参考资料）

又拍云之 Keepalived 高可用部署

VirMach 便宜 VPS

QNews

熱門搜尋