2018 吉林 ccpc Lovers hdu6562

 

题意：维护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:\n",++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\n",qsum(a,b,1,n,1)%mod);}}return 0;
}