2018ccpc吉林 H: LOVERS 线段树

题意：原先有n个空串，两种操作：

题解：对于wrap一个数x的话，那么这个数会变成dxd，这个数的变化过程是d*10^strlen(x)*10+x*10+d，那么我们修改一个区间呢。区间[l,r]也就变化为 d*10*(10^strlen(a[l]) + 10^strlen(a[l+1]).....+ 10^strlen(a[r]) ) + (a[l]+a[l+1]+...+a[r])*10+d*(r-l+1)；所以我们可以通过线段树来维护下区间和(我用s1表示的) 和 (10^strlen(a[l]) + 10^strlen(a[l+1]).....+ 10^strlen(a[r]) )(我用s2表示的)，然后我又设了laz1和laz2，作为当前区间左右添加的数，用来更新两个子区间，lazlen表示10^strlen(laz1)，方便更新子区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll mod=1e9+7;
struct node{int l,r,len;ll s1;  // lenll s2;ll laz1,laz2,lazlen;
}tree[N<<2];
int n,m;
void build(int l,int r,int cur)
{tree[cur].l=l;tree[cur].r=r;tree[cur].len=r-l+1;tree[cur].laz1=0;tree[cur].laz2=0;tree[cur].lazlen=1;tree[cur].s1=r-l+1;tree[cur].s2=0;if(l==r)return;int mid=(r+l)>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);
}
void pushdown(int cur)
{if(tree[cur].lazlen>1){    tree[cur<<1].s2=(tree[cur].laz1*tree[cur<<1].s1%mod*tree[cur].lazlen%mod+tree[cur<<1].s2*tree[cur].lazlen%mod+tree[cur].laz2*tree[cur<<1].len%mod)%mod;tree[cur<<1|1].s2=(tree[cur].laz1*tree[cur<<1|1].s1%mod*tree[cur].lazlen%mod+tree[cur<<1|1].s2*tree[cur].lazlen%mod+tree[cur].laz2*tree[cur<<1|1].len%mod)%mod;tree[cur<<1].s1=(tree[cur<<1].s1*tree[cur].lazlen%mod*tree[cur].lazlen)%mod;tree[cur<<1|1].s1=(tree[cur<<1|1].s1*tree[cur].lazlen%mod*tree[cur].lazlen)%mod;tree[cur<<1].laz1=(tree[cur].laz1*tree[cur<<1].lazlen%mod+tree[cur<<1].laz1)%mod;tree[cur<<1|1].laz1=(tree[cur].laz1*tree[cur<<1|1].lazlen%mod+tree[cur<<1|1].laz1)%mod;tree[cur<<1].laz2=(tree[cur<<1].laz2*tree[cur].lazlen%mod+tree[cur].laz2)%mod;tree[cur<<1|1].laz2=(tree[cur<<1|1].laz2*tree[cur].lazlen%mod+tree[cur].laz2)%mod;tree[cur<<1].lazlen=(tree[cur<<1].lazlen*tree[cur].lazlen)%mod;tree[cur<<1|1].lazlen=(tree[cur<<1|1].lazlen*tree[cur].lazlen)%mod;tree[cur].lazlen=1;tree[cur].laz1=0;tree[cur].laz2=0;}
}
void pushup(int cur)
{tree[cur].s1=(tree[cur<<1].s1+tree[cur<<1|1].s1)%mod;tree[cur].s2=(tree[cur<<1].s2+tree[cur<<1|1].s2)%mod;
}
void update(int pl,int pr,int cur,int d)
{
//  printf("%d %d  -  %d\n",tree[cur].l,tree[cur].r,d);if(pl<=tree[cur].l && tree[cur].r<=pr){tree[cur].s2=(d*tree[cur].s1*10%mod+tree[cur].s2*10%mod+tree[cur].len*d%mod)%mod;//  cout<<tree[cur].s2<<endl;tree[cur].s1=(tree[cur].s1*100)%mod;tree[cur].laz1=(tree[cur].lazlen*d%mod+tree[cur].laz1)%mod;tree[cur].laz2=(tree[cur].laz2*10+d)%mod;tree[cur].lazlen=(tree[cur].lazlen*10)%mod;
//      cout<<tree[cur].s1<<" "<<tree[cur].s2<<" "<<tree[cur].laz1<<" "<<tree[cur].laz2<<" "<<tree[cur].lazlen<<endl;return;}pushdown(cur);if(pl<=tree[cur<<1].r) update(pl,pr,cur<<1,d);if(pr>=tree[cur<<1|1].l) update(pl,pr,cur<<1|1,d);pushup(cur);
}
ll query(int pl,int pr,int cur)
{
//  cout<<tree[cur].l<<" "<<tree[cur].r<<" "<<tree[cur].s1<<" "<<tree[cur].s2<<" "<<tree[cur].laz1<<" "<<tree[cur].laz2<<" "<<tree[cur].lazlen<<endl;if(pl<=tree[cur].l&&tree[cur].r<=pr){return tree[cur].s2;}pushdown(cur);ll res=0;if(pl<=tree[cur<<1].r) res+=query(pl,pr,cur<<1);if(pr>=tree[cur<<1|1].l) res+=query(pl,pr,cur<<1|1);return res%mod;
}
int main()
{int T;int nn=1;char op[10];int l,r,d;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);build(1,n,1);printf("Case %d:\n",nn++);while(m--){scanf("%s%d%d",op,&l,&r);if(op[0]=='w'){scanf("%d",&d);update(l,r,1,d);}else{printf("%lld\n",query(l,r,1));}}}return 0;
}