自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 22:20:01，当前版本为作者最后更新于2025-01-10 15:59:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

有一个长度为 $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 记录。