题意
给定一串长度为 n n n 的数字，数字为 0 ∼ 9 0\sim 9 0∼9 之间的任意一个，下标从 1 1 1 记起。
然后进行 m m m 次区间查询，每次查找区间 [ A , B ] [A,B] [A,B] 的区间和，并在查询结束后将区间里的每一个数都 + 1 +1 +1。特殊地，如果 + 1 +1 +1 前的数字为 9 9 9，那么 + 1 +1 +1 之后就变成了 0 0 0。
请输出每次查询的区间和。
思路
前面做过那么多势能线段树，肯定想要用势能线段树来做。然而发现这是一个区间修改（区间加），那 p u s h d o w n pushdown pushdown 要怎么办呢？如果要写 p u s h d o w n pushdown pushdown 就很难搞最大值，而且修改次数就是 m m m 次， m m m 次都可能干上最大值 10 10 10 ；如果不写 p u s h d o w n pushdown pushdown，等着我们的就是T飞！
但是我们发现，数字出现的范围是 0 ∼ 9 0\sim 9 0∼9，非常少，用一个桶来维护绰绰有余。
于是我们考虑维护区间中 0 ∼ 9 0\sim 9 0∼9 分别有多少个的桶 c n t cnt cnt 数组就好了。引入懒标记 t a g tag tag 表示修改次数，每次修改操作把该区间的 t a g + 1 tag+1 tag+1 ，做一次修改即可。
对于 u u u 区间的修改，要进行 k k k 次修改，集成为一个函数 m o d i modi modi ：每次先把原来桶复制一份到 t e m tem tem 数组，然后把按照 0 ∼ 9 0\sim 9 0∼9的顺序顺次加 k k k 模 10 10 10 进行移位操作。 c n t ( i + k ) m o d 10 ← t e m i , i ∈ [ 0 , 9 ] cnt_{(i+k)\mod 10}\leftarrow tem_i,\ i\in[0,9] cnt(i+k)mod10←temi, i∈[0,9]
void modi(ll u,ll k)
{if(k==0)return;for(int i=0;i<P;i++)tem[i]=T[u].cnt[i],T[u].cnt[i]=0;for(int i=0;i<P;i++)T[u].cnt[(i+k)%P]=tem[i];
}
那么其他就是线段树的基本操作了。建树时每个数位上的数，桶置为 1 1 1 即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ls u<<1
#define rs u<<1|1
const ll N=2.5e5+2,M=1e6+9,P=10;
ll n,m,a[N],tem[P+1];
char c[N];
struct SegT
{struct node{ll cnt[12],tag;}T[N<<4];void modi(ll u,ll k){if(k==0)return;for(int i=0;i<P;i++)tem[i]=T[u].cnt[i],T[u].cnt[i]=0;for(int i=0;i<P;i++)T[u].cnt[(i+k)%P]=tem[i];}void pushup(ll u){for(int i=0;i<=9;i++)T[u].cnt[i]=T[ls].cnt[i]+T[rs].cnt[i]; }void pushdown(ll u){if(T[u].tag){T[ls].tag+=T[u].tag;modi(ls,T[u].tag);T[rs].tag+=T[u].tag;modi(rs,T[u].tag);T[u].tag=0;}}void build(ll u,ll l,ll r){if(l==r){T[u].cnt[a[l]]=1;return;}ll mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(u);}void modify(ll u,ll l,ll r,ll ql,ll qr){if(qr<l||r<ql)return;if(ql<=l&&r<=qr){T[u].tag++;modi(u,1);return;}ll mid=(l+r)>>1;pushdown(u);if(ql<=mid)modify(ls,l,mid,ql,qr);if(qr>mid)modify(rs,mid+1,r,ql,qr);pushup(u);}ll query(ll u,ll l,ll r,ll ql,ll qr){if(qr<l||r<ql)return 0;if(ql<=l&&r<=qr){ll ret=0;for(int i=0;i<=9;i++)ret+=T[u].cnt[i]*i;return ret;}ll mid=(l+r)>>1,ret=0;pushdown(u);if(ql<=mid)ret+=query(ls,l,mid,ql,qr);if(qr>mid)ret+=query(rs,mid+1,r,ql,qr);return ret;}
}A;
int main()
{scanf("%d%d%s",&n,&m,c+1);for(int i=1;i<=n;i++)a[i]=c[i]-'0';A.build(1,1,n);while(m--){ll l,r;scanf("%d%d",&l,&r);printf("%d\n",A.query(1,1,n,l,r));A.modify(1,1,n,l,r);}return 0;
}
