题解：P6357 [COCI2007-2008#3] REDOKS

题意

有一个长度为 n 的数，现在有 m 次询问，每次询问这个数第 l\sim r 位上的各位数字之和。每次询问后 l\sim r 之间的数位上的每个数位增加一，9 增加一变成 0。

思路

我们发现这个问题可以转换为区间查询和区间修改的问题，于是我们可以用线段树来解决。

首先我们记录每个区间内 0\sim 9 分别出现的次数，每次询问时给区间打上懒标记，除了 Push_down 操作，其余基本与普通线段树相同。对于转换，由于我们可能需要一次进行多次转换，转换方式为转换后的数字等于转换前的数字加上转换次数在模 10。

代码

#include<bits/stdc++.h>
#define N 250000
using namespace std;
struct Node{
    int l,r,bj ,w[10];
}a[8*N];
int n,m;
string s;
inline void Push_down(int p){
    int w[10];
    for(int i=0;i<=9;i++){
        w[(i+a[p].bj)%10]=a[p].w[i];
    }
    for(int i=0;i<=9;i++){
        a[p].w[i]=w[i];
    }
    if(a[p].l!=a[p].r){
        a[2*p].bj+=a[p].bj;
        a[2*p+1].bj+=a[p].bj;
    }
    a[p].bj=0;
}
inline void Push_up(int p){
    if(a[p].l==a[p].r){
        if(a[p].bj){
            Push_down(p);
        }
        return;
    }
    if(a[p*2].bj){
        Push_down(p*2);
    }
    if(a[p*2+1].bj){
        Push_down(p*2+1);
    }
    for(int i=0;i<=9;i++){
        a[p].w[i]=a[p*2].w[i]+a[p*2+1].w[i];
    }
}
inline void New_Tree(int p,int l,int r){
    a[p].l=l,a[p].r=r;
    if(l==r){
        a[p].w[s[l]-'0']++;
        return;
    }
    int mid=(l+r>>1);
    New_Tree(p*2,l,mid);
    New_Tree(p*2+1,mid+1,r);
    Push_up(p);
}
inline int sum(int p){
    int w=0;
    for(int i=1;i<=9;i++){
        w+=a[p].w[i]*i;
    }
    return w;
}
inline int find(int p,int l,int r){
    if(a[p].bj){
        Push_down(p);
    }
    if(l<=a[p].l&&r>=a[p].r){
        a[p].bj++;
        int x=sum(p);
        Push_down(p);
        return x;
    }
    int mid=(a[p].l+a[p].r>>1);
    int x;
    if(mid<l){
        x=find(p*2+1,l,r);
    }
    else if(mid>=r){
        x=find(p*2,l,r);
    }
    else{
        x=find(p*2,l,mid)+find(p*2+1,mid+1,r);
    }
    Push_up(p);
    return x;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    cin>>s;
    s=' '+s;
    New_Tree(1,1,n);
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        cout<<find(1,l,r)<<'\n';
    }
    return 0;
}

AC 记录。