【题录】数据结构杂题

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct tag{
	long long ans,b3,e1,b3e1;
};
tag operator + (tag x,tag y){
	tag z;
	z.ans=(x.ans+y.ans)%mod;
	z.b3=(x.b3+y.b3)%mod;
	z.e1=(x.e1+y.e1)%mod;
	z.b3e1=(x.b3e1+y.b3e1)%mod;
	return z;
}
//两个大标记相加为将其小标记相加 
tag operator * (tag x,tag y){
	tag z;
	z.ans=(x.ans*y.ans-x.e1*y.b3%mod+mod)%mod;
	z.b3=(x.b3*y.ans-x.b3e1*y.b3%mod+mod)%mod;
	z.e1=(x.ans*y.e1-x.e1*y.b3e1%mod+mod)%mod;
	z.b3e1=(x.b3*y.e1-x.b3e1*y.b3e1%mod+mod)%mod;
	return z;
}
//两个大标记相乘为将其小标记合并 
struct node{
	tag l,e,g;
};
inline node merge(node x,node y){
	node z;
	z.l=x.e*y.l+x.l*(y.l+y.e+y.g);
	z.e=x.e*y.e;
	z.g=x.e*y.g+x.g*(y.l+y.e+y.g);
	return z;
}
//大标记的合并 
int n,q,a[100010];
node tree[400010];
inline void init(int x,int v){
	tree[x].l.ans=v;
	tree[x].e.ans=1;
	tree[x].g.ans=9-v;
	if(v<1)
	{
		tree[x].l.e1=0;
		tree[x].e.e1=0;
		tree[x].g.e1=1;
	}
	if(v==1)
	{
		tree[x].l.e1=0;
		tree[x].e.e1=1;
		tree[x].g.e1=0;
	}
	if(v>1)
	{
		tree[x].l.e1=1;
		tree[x].e.e1=0;
		tree[x].g.e1=0;
	}
	if(v<3)
	{
		tree[x].l.b3=0;
		tree[x].e.b3=0;
		tree[x].g.b3=1;
	}
	if(v==3)
	{
		tree[x].l.b3=0;
		tree[x].e.b3=1;
		tree[x].g.b3=0;
	}
	if(v>3)
	{
		tree[x].l.b3=1;
		tree[x].e.b3=0;
		tree[x].g.b3=0;
	}
	tree[x].l.b3e1=0;
	tree[x].e.b3e1=0;
	tree[x].g.b3e1=0;
}
//线段树叶子节点的分类讨论 
inline void pushup(int x){
	tree[x]=merge(tree[x*2],tree[x*2+1]);
}
void build(int l,int r,int x){
	if(l==r)
	{
		init(x,a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	pushup(x);
}
void change(int l,int r,int x,int k,int v){
	if(l==r)
	{
		init(x,v);
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid)change(l,mid,x*2,k,v);
	else change(mid+1,r,x*2+1,k,v);
	pushup(x);
}
node ask(int l,int r,int x,int ll,int rr){
	if(l>=ll&&r<=rr)return tree[x];
	int mid=(l+r)>>1;
	if(rr<=mid)return ask(l,mid,x*2,ll,rr);
	if(ll>mid)return ask(mid+1,r,x*2+1,ll,rr);
	return merge(ask(l,mid,x*2,ll,rr),ask(mid+1,r,x*2+1,ll,rr));
}
//线段树维护标记 
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		a[i]=c-'0';
	}
	build(1,n,1);
	printf("%lld\n",(tree[1].l.ans+tree[1].e.ans)%mod);
	while(q--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int l,r;
			scanf("%d%d",&l,&r);
			node s=ask(1,n,1,l,r);
			printf("%lld\n",(s.l.ans+s.e.ans)%mod);
		}
		else
		{
			int k,v;
			scanf("%d%d",&k,&v);
			change(1,n,1,k,v);
		}
	}
	return 0;
}