题意：维护n个串(也可以是说是大数） 一开始为空 （不是0 ）
操作1 upsum l r x l到r串每个串的左右都放上x
操作2 区间求和
mod除了除法要用逆元以外 几乎可以任意使用 这题甚至截取一段数字使用mod
比赛的时候就是因为不知道可以这样mod 甚至想用大数
因为标记是有先后顺序的 比赛的时候想开个vector来存标记 但是不太现实
可以将标记放到不同数位上 这样不仅方便了接下来的操作 并且维护了标记的顺序关系
collen表示懒标记长度 len表示t值的长度 左右懒标记是镜像的 方便维护 左懒标记放左边 右懒标记放右边
注意down 和sum的细节
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(ll i=(a);i<=(b);i++) #define repp(i,a,b) for(ll i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<ll,ll>pii; ////////////////////////////////// const ll N=2e6+10; const ll mod=1e9+7; ll t[N<<2],len[N<<2],col1[N<<2],col2[N<<2],collen[N<<2]; void up(ll pos) { t[pos]=(t[pos<<1]+t[pos<<1|1])%mod; len[pos]=(len[pos<<1]+len[pos<<1|1])%mod; } void build(ll l,ll r,ll pos) { t[pos]=col1[pos]=col2[pos]=0; collen[pos]=1; if(l==r){len[pos]=1;return;} ll m=(l+r)>>1;build(lson);build(rson);up(pos); } void down(ll m,ll pos) { if(collen[pos]>1) { col1[pos<<1]=(col1[pos]*collen[pos<<1]%mod+col1[pos<<1])%mod; col1[pos<<1|1]=(col1[pos]*collen[pos<<1|1]%mod+col1[pos<<1|1])%mod; col2[pos<<1]=(col2[pos]+collen[pos]*col2[pos<<1]%mod)%mod; col2[pos<<1|1]=(col2[pos]+collen[pos]*col2[pos<<1|1]%mod)%mod; t[pos<<1]=( t[pos<<1]*collen[pos]%mod+col2[pos]*(m-(m>>1))%mod +col1[pos]*len[pos<<1]%mod*collen[pos]%mod ) %mod; t[pos<<1|1]=( t[pos<<1|1]*collen[pos]%mod+col2[pos]*(m>>1)%mod +col1[pos]*len[pos<<1|1]%mod*collen[pos]%mod ) %mod; len[pos<<1]=(len[pos<<1]*collen[pos]%mod*collen[pos])%mod; len[pos<<1|1]=(len[pos<<1|1]*collen[pos]%mod*collen[pos])%mod; collen[pos<<1]=(collen[pos<<1]*collen[pos])%mod; collen[pos<<1|1]=(collen[pos<<1|1]*collen[pos])%mod; col1[pos]=0;col2[pos]=0; collen[pos]=1; } } void upsum(ll L,ll R,ll v,ll l,ll r,ll pos) { if(L<=l&&r<=R) { t[pos]=(t[pos]*10%mod+v*(r-l+1)%mod+len[pos]*10*v%mod )%mod; len[pos]=len[pos]*100%mod; col1[pos]=(col1[pos]+v*collen[pos]%mod)%mod; col2[pos]=(col2[pos]*10%mod+v)%mod; collen[pos]=collen[pos]*10%mod; down(r-l+1,pos); return ; } down(r-l+1,pos);ll m=(l+r)>>1; if(L<=m)upsum(L,R,v,lson);if(R>m)upsum(L,R,v,rson);up(pos); } ll qsum(ll L,ll R,ll l,ll r,ll pos) { ll ans=0;if(L<=l&&r<=R)return t[pos]%mod; down(r-l+1,pos);ll m=(l+r)>>1; if(L<=m)ans=(ans+qsum(L,R,lson))%mod ;if(R>m)ans=(ans+qsum(L,R,rson))%mod;return ans; } ll n,m; char s[10]; ll c,a,b; int main() { ll cas;cin>>cas;int kase=0; while(cas--) { printf("Case %d: ",++kase); cin>>n>>m;build(1,n,1); while(m--) { RS(s); if(s[0]=='w')scanf("%lld%lld%lld",&a,&b,&c),upsum(a,b,c,1,n,1); else scanf("%lld%lld",&a,&b),printf("%lld ",qsum(a,b,1,n,1)%mod); } } return 0; }