题解：P13983 数列分块入门 8

· · 题解

明明是数列分块的套题，怎么算法标签里只有 ODT？

分析

散块好做，下面讨论整块的做法。

首先想到将原数列离散化一下，然后设 f_{i,j} 表示前 i 个块中 j 出现的次数，用前缀和解决。但这题带修，所以这个做法搞不了。

考虑别的做法。

我们发现每次操作都会推平一个区间，所以可能会存在大段大段的相同的数。于是我们想到，可以设 flag_i 表示第 i 块是不是都为同一个数，这样就可以方便地统计整块的贡献了。在此基础上，我们再设 la_i 表示如果第 i 块全为某一个数，那么这个数是多少。

针对第 i 块，我们应该怎么做呢？

假如 flag_i 为真且 la_i=c，那么第 i 块产生的贡献就是它的块长，可以直接加入答案。

那么如果 flag_i 为真，但 la_i 与 c 不等呢？这时第 i 块不会对答案产生贡献，于是我们把 la_i 赋值为 c，然后跳过这个块即可。

而 flag_i 为假时，我们直接遍历这个块中的每个数，暴力统计、暴力修改，然后把 flag_i 赋为真，la_i 赋为 c 即可。

于是代码就很好写了。

代码

码风魔怔，欢迎来喷。

#include<iostream>
#include<cmath>
using namespace std;

const int N=5e5+5;
const int M=710;

int n;

int a[N];

int ans[N];

namespace OIfast{

    #define gc getchar()

    inline int read(){
        int n=0;char c=gc;
        while(!isdigit(c))c=gc;
        while(isdigit(c))n=(n<<3)+(n<<1)+(c^48),c=gc;
        return n;
    }

}using namespace OIfast;

namespace FK{

    int k/*块长*/,tot/*块长*/;

    short loc[N]/*loc[i] -> 第 i 个数在第几块*/;
    int L[M]/*块长*/,R[M]/*R[i] -> 第 i 块的右端点*/,la[M]/*含义见上*/;
    bool flag[M]/*含义见上*/;

    inline void pushup(int i){//更新 flag
        flag[i]=1;for(int j=L[i]+1;j<=R[i];++j)if(a[j]^a[j-1]){flag[i]=0;continue ;}
        if(flag[i])la[i]=a[L[i]];
        return ;
    }

    inline void pushdown(int i){//下放标记
        if(flag[i])for(int j=L[i];j<=R[i];++j)a[j]=la[i];
        return ;
    }

    inline void init(){
        k=sqrt(n),tot=ceil((1.0*n)/(1.0*k));
        for(int i=1;i<=tot;++i){
            L[i]=(i-1)*k+1,R[i]=min(L[i]+k-1,n);
            for(int j=L[i];j<=R[i];++j)loc[j]=i;
            pushup(i);
        }
        return ;
    }

    inline int qry(int l,int r,int v){
        int res=0;
        if(loc[l]==loc[r]){
            pushdown(loc[l]);
            for(int i=l;i<=r;++i)res+=(a[i]==v),a[i]=v;
            pushup(loc[l]);
        }else{
            pushdown(loc[l]),pushdown(loc[r]);
            for(int i=l;i<=R[loc[l]];++i)res+=(a[i]==v),a[i]=v;
            for(int i=L[loc[r]];i<=r;++i)res+=(a[i]==v),a[i]=v;
            for(int i=loc[l]+1;i<=loc[r]-1;++i){
                if(flag[i]){
                    if(la[i]==v)res+=R[i]-L[i]+1;
                    else la[i]=v;
                }else{
                    for(int j=L[i];j<=R[i];++j)res+=(a[j]==v),a[j]=v;
                    flag[i]=1,la[i]=v;
                }
            }
            pushup(loc[l]),pushup(loc[r]);
        }
        return res;
    }

}using namespace FK;

inline void work(int i){
    int l=read(),r=read(),v=read();
    return ans[i]=qry(l,r,v),void();
}

signed main(){
    n=read();for(int i=1;i<=n;++i)a[i]=read();
    init();for(int i=1;i<=n;++i)work(i);
    for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
    return 0;
}

代码里的快读没有考虑负数，按理说会挂（可以在这里看到 hack 数据），但并不影响它能过。