大意: 有$n$个数字串, 初始为空, 两种操作(1)把$[l,r]$范围的所有数字串首位添加数位$d$ (2)询问$[l,r]$区间和
假设添加的数为$L$, $L$位数为$H$, $L$翻转后乘上$10^H$为$R$
假设$x$的位数为$h$, 那么$x$就会变为$R10^h+x10^H+L$
区间和$s_1$变为$R\sum 10^h+s_110^H+L(r-l+1)$.
再维护一个$s_2=\sum 10^h$即可
#include <iostream> #include <sstream> #include <algorithm> #include <cstdio> #include <cmath> #include <set> #include <map> #include <queue> #include <string> #include <cstring> #include <bitset> #include <functional> #include <random> #define REP(i,a,n) for(int i=a;i<=n;++i) #define PER(i,a,n) for(int i=n;i>=a;--i) #define hr putchar(10) #define pb push_back #define lc (o<<1) #define rc (lc|1) #define mid ((l+r)>>1) #define ls lc,l,mid #define rs rc,mid+1,r #define x first #define y second #define io std::ios::sync_with_stdio(false) #define endl '\n' #define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;}) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int P = 1e9+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;} inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;} //head const int N = 1e5+10; struct _ { int s1,s2,pre,suf,h; void upd(int H, int L, int R, int len) { s1 = ((ll)s1*H+(ll)len*L+(ll)s2*R)%P; s2 = (ll)s2*H%P*H%P; pre = ((ll)pre*H+L)%P; suf = ((ll)suf*H+(ll)R*h%P*h)%P; h = (ll)h*H%P; } _ operator + (const _ &rhs) const { _ ret; ret.s1 = (s1+rhs.s1)%P; ret.s2 = (s2+rhs.s2)%P; ret.pre = ret.suf = 0; ret.h = 1; return ret; } } tr[N<<2]; void pd(int o, int l, int r) { if (tr[o].h!=1) { tr[lc].upd(tr[o].h,tr[o].pre,tr[o].suf,mid-l+1); tr[rc].upd(tr[o].h,tr[o].pre,tr[o].suf,r-mid); tr[o].h=1,tr[o].pre=tr[o].suf=0; } } void add(int o, int l, int r, int ql, int qr, int d) { if (ql<=l&&r<=qr) return tr[o].upd(10,d,d*10,r-l+1); pd(o,l,r); if (mid>=ql) add(ls,ql,qr,d); if (mid<qr) add(rs,ql,qr,d); tr[o] = tr[lc]+tr[rc]; } int query(int o, int l, int r, int ql, int qr) { if (ql<=l&&r<=qr) return tr[o].s1; pd(o,l,r); int ans = 0; if (mid>=ql) ans+=query(ls,ql,qr); if (mid<qr) ans+=query(rs,ql,qr); return ans%P; } void build(int o, int l, int r) { if (l==r) tr[o] = {0,1,0,0,1}; else build(ls),build(rs),tr[o]=tr[lc]+tr[rc]; } int n, m; void work() { scanf("%d%d",&n,&m); build(1,1,n); while (m--) { char s[10]; int l,d,r; scanf("%s%d%d",s,&l,&r); if (s[0]=='w') scanf("%d",&d),add(1,1,n,l,r,d); else printf("%d\n",query(1,1,n,l,r)); } } int main() { int t=rd(); REP(i,1,t) { printf("Case %d:\n",i); work(); } }