P6357 [COCI 2007/2008 #3] REDOKS 题解

lzh0220 · 2025-03-27 19:31:24 · 题解

思路

题解区里基本上都是线段树做法，那我来说一下分块。

首先我们需要维护每个块内 0 到 9 分别出现的次数。对于每个块，维护一个类似懒标记的东西，记录这个整块 +1 的次数。

查询时直接暴力修改散块，对于整块打上懒标记，求出答案即可。

时间复杂度 O(n\sqrt n)，实测跑的飞快。

code

const int N=250010,M=510;
int bl[N],sum[M][10],t[M],a[N],to[10][10];
signed main(){
    for(int i=0;i<=9;i++)for(int j=0;j<=9;j++)to[i][j]=(i+j)%10;
    int n=read(),m=read(),len=sqrt(n);
    for(int i=1;i<=n;i++){
        bl[i]=(i-1)/len+1;
        a[i]=getch()-'0';
        sum[bl[i]][a[i]]++;
    }
    while(m--){
        int l=read(),r=read();
        if(t[bl[l]]){
            for(int i=0;i<=9;i++)sum[bl[l]][i]=0;
            for(int i=bl[l]*len-len+1;i<=bl[l]*len;i++){
                a[i]=to[a[i]][t[bl[l]]];
                sum[bl[l]][a[i]]++;
            }t[bl[l]]=0;
        }
        if(t[bl[r]]){
            for(int i=0;i<=9;i++)sum[bl[r]][i]=0;
            for(int i=bl[r]*len-len+1;i<=bl[r]*len;i++){
                a[i]=to[a[i]][t[bl[r]]];
                sum[bl[r]][a[i]]++;
            }t[bl[r]]=0;
        }int ans=0;
        if(bl[l]==bl[r]){
            for(int i=l;i<=r;i++)ans+=a[i];
            printf("%lld\n",ans);
            for(int i=l;i<=r;i++){
                sum[bl[i]][a[i]]--;
                a[i]=to[a[i]][1];
                sum[bl[i]][a[i]]++;
            }continue;
        }
        for(int i=l;i<=bl[l]*len;i++)ans+=a[i];
        for(int i=bl[r]*len-len+1;i<=r;i++)ans+=a[i];
        for(int i=l;i<=bl[l]*len;i++){
            sum[bl[i]][a[i]]--;
            a[i]=to[a[i]][1];
            sum[bl[i]][a[i]]++;
        }
        for(int i=bl[r]*len-len+1;i<=r;i++){
            sum[bl[i]][a[i]]--;
            a[i]=to[a[i]][1];
            sum[bl[i]][a[i]]++;
        }
        for(int i=bl[l]+1;i<=bl[r]-1;i++){
            for(int j=0;j<=9;j++)ans+=to[j][t[i]]*sum[i][j];
            t[i]=to[t[i]][1];
        }printf("%lld\n",ans);
    }
    ret 0;
}