题意：
给定长度为n的串S，由字符A和B组成， 现在要进行q次操作，操作有两种： (1,L,R)：将[L,R]翻转，A变成B，B变成A。 (2,L,R,A,B)：计算f(L,R,A,B)的值并输出，f函数定义如下：
function
f(L
, R
, A
, B
):
FOR i from L to R
if S
[i
] = 'A'
A
= A
+ B
else
B
= A
+ B
return (A
, B
)
答案对1e9+7取模
数据范围：n,q<=1e5，0<=操作2的A和B<=1e9
解法：
观察到函数对A和B的修改类似斐波那契,可以想到矩阵转移. 开一颗线段树,每个节点维护一个转移矩阵就行了. 不过还有区间取反操作,好像比较麻烦, 看了别人代码发现可以在每个节点同时维护一个翻转的矩阵, 例如本来这个区间是AAB,同时维护一个BBA, 然后交换的时候直接交换就行了,非常方便.
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=1e5+5;
const int mod
=1e9+7;
char s
[maxm
];
int n
,q
;
struct Node
{
int a
[2][2];
void initA(){
a
[0][0]=a
[1][1]=a
[1][0]=1;
a
[0][1]=0;
}
void initB(){
a
[0][0]=a
[1][1]=a
[0][1]=1;
a
[1][0]=0;
}
Node
operator*(const Node
& b
)const{
Node ans
={
0,0,
0,0,
};
for(int k
=0;k
<2;k
++){
for(int i
=0;i
<2;i
++){
for(int j
=0;j
<2;j
++){
ans
.a
[i
][j
]=(ans
.a
[i
][j
]+a
[i
][k
]*b
.a
[k
][j
])%mod
;
}
}
}
return ans
;
}
};
struct Tree
{
Node a
[maxm
<<2][2];
int laz
[maxm
<<2];
void pushup(int node
){
for(int j
=0;j
<2;j
++){
a
[node
][j
]=a
[node
*2][j
]*a
[node
*2+1][j
];
}
}
void pushdown(int node
){
if(laz
[node
]){
swap(a
[node
*2][0],a
[node
*2][1]);
swap(a
[node
*2+1][0],a
[node
*2+1][1]);
laz
[node
*2]^=1;
laz
[node
*2+1]^=1;
laz
[node
]=0;
}
}
void build(int l
,int r
,int node
){
if(l
==r
){
if(s
[l
]=='A'){
a
[node
][0].initA();
a
[node
][1].initB();
}else{
a
[node
][0].initB();
a
[node
][1].initA();
}
return ;
}
int mid
=(l
+r
)/2;
build(l
,mid
,node
*2);
build(mid
+1,r
,node
*2+1);
pushup(node
);
}
void update(int st
,int ed
,int l
,int r
,int node
){
if(st
<=l
&&ed
>=r
){
swap(a
[node
][0],a
[node
][1]);
laz
[node
]^=1;
return ;
}
pushdown(node
);
int mid
=(l
+r
)/2;
if(st
<=mid
)update(st
,ed
,l
,mid
,node
*2);
if(ed
>mid
)update(st
,ed
,mid
+1,r
,node
*2+1);
pushup(node
);
}
Node
ask(int st
,int ed
,int l
,int r
,int node
){
if(st
<=l
&&ed
>=r
)return a
[node
][0];
pushdown(node
);
int mid
=(l
+r
)/2;
Node ans
={
1,0,
0,1,
};
if(st
<=mid
)ans
=ans
*ask(st
,ed
,l
,mid
,node
*2);
if(ed
>mid
)ans
=ans
*ask(st
,ed
,mid
+1,r
,node
*2+1);
return ans
;
}
}t
;
signed main(){
cin
>>n
>>q
;
scanf("%s",s
+1);
t
.build(1,n
,1);
while(q
--){
int op
;cin
>>op
;
if(op
==1){
int l
,r
;cin
>>l
>>r
;
t
.update(l
,r
,1,n
,1);
}else{
int l
,r
,a
,b
;cin
>>l
>>r
>>a
>>b
;
Node temp
=t
.ask(l
,r
,1,n
,1);
int ans1
=(temp
.a
[0][0]*a
+temp
.a
[1][0]*b
)%mod
;
int ans2
=(temp
.a
[0][1]*a
+temp
.a
[1][1]*b
)%mod
;
cout
<<ans1
<<' '<<ans2
<<endl
;
}
}
return 0;
}
