矩阵乘法没有结合律

虽然这个题干就告诉了我们这个题要用矩阵，但是考场上是想不到正解的(想到线段树已经是极限了)

首先考虑一下我们怎么把这两个奇怪的操作转化为矩阵的形式，我这里就直接上公式了

$\begin{bmatrix}a&b\\ \end{bmatrix}\times \begin{bmatrix}0&1\\1&0\\ \end{bmatrix}= \begin{bmatrix}b&a\\ \end{bmatrix}，\begin{bmatrix}a&b\\ \end{bmatrix}\times \begin{bmatrix}114514&1\\7&0\\ \end{bmatrix}= \begin{bmatrix}114514a+7b&a\\ \end{bmatrix}$

然后，因为这题涉及区间修改与查询，很典的一个线段树模板，直接套就可以过了

这里有一个小技巧，为了避免查询操作时有太多的较大方阵相乘浪费时间，这里我们会直接将答案矩阵传入并乘上各部分答案(好像还有少了递归这里省的时间)

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=2e5+10, mod=998244353;

struct matrix
{
	int n, m;
	ll mat[2][2];
	
	matrix( int _n,int _m )
	{
		n=_n, m=_m;
		for( int i=0;i<n;i++ ) 
			for( int j=0;j<m;j++ )
				mat[i][j]=0;
	}
	
    void print()
    {
        for( int i=0;i<n;i++ )
            for( int j=0;j<m;j++ )
                cout<<mat[i][j]<<" \n"[j == m-1];
    }

	matrix operator* ( const matrix &a )const
	{
		matrix ans( n,a.m );
        for( int k=0;k<m;k++ )
		    for( int i=0;i<n;i++ )
			    for( int j=0;j<a.m;j++ )
					ans.mat[i][j]+=mat[i][k]*a.mat[k][j], ans.mat[i][j]%=mod;
		return ans;
	}
};

string s;
matrix X( 2,2 ), Y( 2,2 );

struct segment_tree
{
    int l, r;
    int rev;
    matrix val[2]={ matrix( 0,0 ),matrix( 0,0 ) };
}st[N<<2];

void build( int p,int l,int r )
{
    st[p].l=l, st[p].r=r, st[p].rev=0;;
    if( l == r )
    {
        if( s[l-1] == 'X' )
            st[p].val[0]=X, st[p].val[1]=Y;
        else 
            st[p].val[0]=Y, st[p].val[1]=X;
        
        return ;
    }
    int mid=( l+r )>>1;
    build( p<<1,l,mid );
    build( p<<1|1,mid+1,r );
    st[p].val[0]=st[p<<1].val[0]*st[p<<1|1].val[0];
    st[p].val[1]=st[p<<1].val[1]*st[p<<1|1].val[1];
}

void updata( int p )
{
    if( st[p].rev )
    {
        swap( st[p<<1].val[0],st[p<<1].val[1] );
        st[p<<1].rev^=1;
        swap( st[p<<1|1].val[0],st[p<<1|1].val[1] );
        st[p<<1|1].rev^=1;
        st[p].rev^=1;
    }
}

void change( int p,int l,int r )
{
    if( st[p].l >= l && st[p].r <= r )
    {
        swap( st[p].val[0],st[p].val[1] );
        st[p].rev^=1;
        return ;
    } 
    updata( p );
    int mid=( st[p].l+st[p].r )>>1;
    if( mid >= l ) change( p<<1,l,r );
    if( mid < r ) change( p<<1|1,l,r );
    st[p].val[0]=st[p<<1].val[0]*st[p<<1|1].val[0];
    st[p].val[1]=st[p<<1].val[1]*st[p<<1|1].val[1];
}

void ask( int p,int l,int r,matrix &ans )
{
    if( st[p].l >= l && st[p].r <= r )
    {
        ans=ans*st[p].val[0];
        return ;
    } 
    updata( p );
    int mid=( st[p].l+st[p].r )>>1;
    if( mid >= l ) ask( p<<1,l,r,ans );
    if( mid < r ) ask( p<<1|1,l,r,ans );
}

int main()
{	
	// freopen( "txt.in","r",stdin );
	std::ios::sync_with_stdio( false );
	cin.tie( nullptr );
	cout.tie( nullptr );
	int n, q;
	cin>>n>>s>>q;
    X.mat[0][1]=X.mat[1][0]=1, X.mat[0][0]=X.mat[1][1]=0;
    Y.mat[0][0]=114514, Y.mat[0][1]=1, Y.mat[1][0]=7, Y.mat[1][1]=0;
    build( 1,1,n );
	for( int i=1, op, l, r;i<=q;i++ )
	{
		cin>>op>>l>>r;
		if( op == 1 )
            change( 1,l,r );
        else
        {
            int a, b;
            cin>>a>>b;
            matrix ans( 1,2 );
            ans.mat[0][0]=a, ans.mat[0][1]=b;
            ask( 1,l,r,ans );
            ans.print();
        }
	}
}