题解：P13983 数列分块入门 8

· · 题解

  1. 对于左右散块，我们下放并清空左右散块的懒标记，其中每有一个元素为 k，答案就加 1。然后把左右散块的部分全赋值成 k。

  2. 对于每个整块，如果这个块有懒标记，若懒标记为 k，则答案加块长，然后把懒标记赋为 k。否则遍历整个块，答案累加其中为 k 的元素的个数，然后把所有元素和这个块的懒标记改为 k。

复杂度 O(n\sqrt n)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,cnt,q,x,y,k,a[N],bel[N],L[N],R[N],lz[N],blo;
void build(int n){
    blo=sqrt(n);
    cnt=(n+blo-1)/blo;
    for(int i=1;i<=cnt;i++){
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    R[cnt]=n;
    for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
    memset(lz,-1,sizeof lz);
}
void upd(int x){
    if(lz[x]==-1) return;
    for(int i=L[x];i<=R[x];i++) a[i]=lz[x];
    lz[x]=-1;
}
int qsum(int x,int y,int k){
    int ans=0;
    if(bel[x]==bel[y]){
        upd(bel[x]);
        for(int i=x;i<=y;i++){
            if(a[i]!=k) a[i]=k;
            else ans++;
        }
        return ans;
    }
    upd(bel[x]);
    for(int i=x;i<=R[bel[x]];i++){
        if(a[i]!=k) a[i]=k;
        else ans++;
    }
    upd(bel[y]);
    for(int i=L[bel[y]];i<=y;i++){
        if(a[i]!=k) a[i]=k;
        else ans++;
    }
    for(int i=bel[x]+1;i<bel[y];i++){
        if(lz[i]!=-1){
            if(lz[i]!=k) lz[i]=k;
            else ans+=blo;
        }
        else{
            for(int j=L[i];j<=R[i];j++){
                if(a[j]!=k) a[j]=k;
                else ans++;
            }
            lz[i]=k;
        }
    }
    return ans;
}
signed main(){
    cin>>n;
    q=n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(n);
    while(q--){
        cin>>x>>y>>k;
        cout<<qsum(x,y,k)<<endl;
    }
}