题解：P13983 数列分块入门 8

Zhangxm2012 · 2025-09-08 19:55:55 · 题解

非常好，LOJ 上的题洛谷有了（双倍经验）。

既然标题写的是分块，那就用分块做吧。分块的时间复杂度为 O(n\sqrt{n})，证明如下（毕竟是入门，本人也才在今年八月得知）：

若记块长为 s，考虑一次操作（左右端点用 l,r 表示，n 为序列长）

• 若 l,r 在同一块内，最坏复杂度为 O(s)；
• 若 l,r 不在同一块内，分三块计算：以 l 为开头的不完整的一段、中间的完整块、和以 r 为结尾的不完整的一段，最坏复杂度为 O(\frac{n}{s}+s)
• 综上，最坏复杂度为 O(\frac{n}{s}+s) 在 s=\sqrt{n} 时取到最小值 O(\sqrt{n})。

本题的数据范围为 1\le n \le 300000，O(n\sqrt{n}) 时能通过的。

好的，回归正题。

因为此题有区间覆盖，不难想到给每个区间打标记，blk_{k} 表示第 k(k\ge0) 块整体的数，f_k 表示区间是否完全覆盖，即同一个数。

修改的时候一起统计：以 l 为开头的不完整的一段、和以 r 为结尾的不完整的一段、中间的完整块。 其中前两个是一样的：若区间不是整块的，暴力循环计数；若是整块的并且数为 c，ans\gets ans+(r-l+1)，否则就下放标记，将要修改的修改掉就行了，再把这个区间的 f \gets 0。
第二个也差不多：枚举所有的块，若是整块就直接加，否则再暴力循环统计即可，注意 blk 和 f 的更改。

#include<bits/stdc++.h>
using namespace std;
const int N=5004;
int n,m,k,a[N*N],blk[N],f[N],ans;
void U(int l,int r,int x){
    int kk=l/k;
    if(!f[kk]){
        for(int i=l;i<=r;i++){
            if(a[i]==x){
                ans++;
            }
            a[i]=x;
        }
    }
    else{
        if(blk[kk]==x){
            ans+=(r-l+1);
        }
        else{
            for(int i=kk*k;i<(kk+1)*k;i++){
                a[i]=blk[kk];
            }
            for(int i=l;i<=r;i++){
                a[i]=x;
            }
            f[kk]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    k=sqrt(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        int l,r,c;
        ans=0;
        cin>>l>>r>>c;
        l--,r--;
        if(l/k==r/k){
            U(l,r,c);
        }
        else{
            U(l,(l/k+1)*k-1,c);
            U(r/k*k,r,c);
            for(int i=l/k+1;i<r/k;i++){
                if(f[i]==0){
                    for(int j=i*k;j<i*k+k;j++){
                        if(a[j]==c){
                            ans++;
                        }
                    }
                    blk[i]=c;
                    f[i]=1;
                }
                else{
                    if(blk[i]==c){
                        ans+=k;
                    }
                    else{
                        blk[i]=c;
                    }
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}