分块(一)

  • 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]\) 的计算

  1. i-1 是为了保证第一个块有 \(len\) 个元素,而不是 \(len-1\) 个;
  2. +1 是为了让第一个块的编号为 \(1\),而不是 \(0\)

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

  1. 左右端点在同一个块中,枚举整个区间暴力求解

  2. 左右端点在不同的块中:

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

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

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

有一张图,或许能帮助你理解:

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

需要一点高中数学知识:(真的只有一点,不是亿点)

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

  1. 左右端点在同一个块中,暴力枚举整个块,复杂度最坏为 \(O(len)\)

  2. 左右端点不在同一个块中,答案由三部分组成:以 \(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\) 个操作,操作涉及区间加法,单点查值。

  • 区间增加

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

  1. 对于 完整块,利用数组 \(b\) 存储对于块整体加的值,不必对于每一个 \(a[i]\) 做加法;
  2. 对于 不完整块左右端点在同一个块中,暴力枚举,对 \(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:

  1. 对于完整块的操作,for 中的 \(i\) 表示块的编号,而不是元素的编号;
  2. \(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 存储每一个块所有元素的值,方便进行二分查找。

  1. 对于 完整块,二分对应块的全部元素,统计个数;
  2. 对于 不完整块左右端点在同一个块中,暴力枚举,统计 \(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;
}
  • 区间求和
  1. 对于 完整块,直接返回数组 \(s\) 的值即可;
  2. 对于 不完整块左右端点在同一个块中,暴力枚举每一个点,累加每一个点的值。
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: AddPow 函数:在函数中进行 \(\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;
}

二、一些想法

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

    它会根据查询内容的不同写法发生很大变化,同时 vector 似乎发挥了很大作用

  2. 还有一些题,先不写了,这些基本的板子题先写出来,然后去写莫队啦༼ つ ◕_◕ ༽つ

    其他题有时间了再写,到时候再写下一个分块的博客吧

  3. 这篇博客只写了半天,和上篇单调队列相比,时间少了好多

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

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