k 题 矩阵乘法+线段树做法

k 题 矩阵乘法+线段树做法

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#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 endl "\n"
#define pb push_back
#define be begin()
#define ed end()
#define fi first
#define se second
#define mid (l+r)/2
#define ls i<<1
#define rs i<<1|1
#define ins insert
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int dx[5]={0,1,-1,0,0};
const int dy[5]={0,0,0,-1,1};
ll ksm(ll a,ll b,int mod){
	if(b==0) return 1;
	if(b==1) return a%mod;
	ll midd=ksm(a,b>>1,mod);
	if(b&1) return midd*midd%mod*a%mod;
	else return midd*midd%mod;
}
ll inv(ll x,int mod){
	return ksm(x,mod-2,mod);
}
#define mod int(1e9+7)
ll om(ll x){
	return (x%mod+mod)%mod;
}
struct mar{
	int r,c;
	int e[3][3];
    void print(){
		rep(i,0,r-1){
			rep(j,0,c-1) cout<<e[i][j]<<" ";
			cout<<endl;
		}
	}
} A,B,C,I;
mar operator + (mar a,mar b){
	mar c;
	memset(c.e,0,sizeof(c.e));
	c.r=a.r,c.c=b.c;
	for(int k=0;k<a.c;k++){
		rep(i,0,a.r-1){
			rep(j,0,b.c-1)
				c.e[i][j]=om(om(1ll*a.e[i][k]*b.e[k][j])+c.e[i][j]);		
		}
	}
	return c;
}
#define N 200100
mar t[N<<2];
char s[N];
void ch(int i,int l,int r,int pos,mar k){
	if(l==r&&r==pos){
		t[i]=k;
		return;
	}
	if(pos<=mid) ch(ls,l,mid,pos,k);
	else ch(rs,mid+1,r,pos,k);
	t[i]=t[ls]+t[rs];
}
mar que(int i,int l,int r,int cl,int cr){
	if(l>=cl&&r<=cr) return t[i];
	if(l>cr||r<cl) return I;
	return que(ls,l,mid,cl,cr)+que(rs,mid+1,r,cl,cr);
}
void build(int i,int l,int r){
	if(l==r){
		if(s[l]=='Y') t[i]=A;
		else if(s[l]=='B') t[i]=B;
		else t[i]=C;
		return;
	}
	build(ls,l,mid);build(rs,mid+1,r);
	t[i]=t[ls]+t[rs];
}
mar init;
void solve(){
	int n,q;
	cin>>n>>q;
	rep(i,0,2) I.e[i][i]=1;
	I.r=I.c=3;
	A.r=A.c=3;
	B.r=B.c=3;
	C.r=C.c=3;
	rep(i,0,2) A.e[i][2]=1;
	rep(i,0,2) A.e[i][i]=1;
	rep(i,0,2) B.e[i][2]=1;
	rep(i,0,2) B.e[0][i]=1;
	B.e[0][1]=0;
	rep(i,0,2) C.e[i][2]=1;
	rep(i,0,2) C.e[0][i]=1;
	C.e[1][1]=2;
	init.r=3,init.c=1;
	init.e[2][0]=1;
	/*
	A.print();
	B.print();
	C.print();
	*/
	rep(i,1,n){
		cin>>s[n-i+1];
	}
	build(1,1,n);
	rep(i,1,q){
		int op;
		cin>>op;
		if(op==1){
			int p;char c;
			cin>>p>>c;
			if(c=='Y') ch(1,1,n,n-p+1,A);
			else if(c=='B') ch(1,1,n,n-p+1,B);
			else ch(1,1,n,n-p+1,C);
		}
		else{
			int l,r;cin>>l>>r;
			mar ans=que(1,1,n,n-r+1,n-l+1)+init;
			//ans.print();
			cout<<ans.e[0][0]<<endl;
		}
	}
}
int main(){
	IOS
	int t=1;//cin>>t;
	while(t--) solve();
	return 0;
}