已经是啥也不会了呜呜呜
考虑这个 \(A=A+B\)，\(B=A+B\) 是可以表达成矩阵形式的。
\(\begin{bmatrix} a&b \end{bmatrix}\begin{bmatrix}1&0\\1&1\end{bmatrix}=\begin{bmatrix} a+b&b \end{bmatrix}\)
\(\begin{bmatrix} a&b \end{bmatrix}\begin{bmatrix}1&1\\0&1\end{bmatrix}=\begin{bmatrix} a&a+b \end{bmatrix}\)
那么就可以用线段树维护矩阵了。
但是还有翻转操作，手玩后发现若一个区间的原矩阵为：
\(\begin{bmatrix}p&q\\r&s\end{bmatrix}\)
那么翻转后的矩阵变成：
\(\begin{bmatrix}s&r\\q&p\end{bmatrix}\)
可以用数学归纳法证明，这里不展开。
具体细节看代码。
Code：
#include <bits/stdc++.h>
using namespace std;
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
typedef long long ll;
const int N = 100005, mod = 1e9 + 7;
int n, Q;
char s[N];
struct mat {
int a[2][2];
mat (int x = 0, int y = 0, int z = 0, int w = 0) {
a[0][0] = x, a[0][1] = y, a[1][0] = z, a[1][1] = w;
}
mat operator * (const mat &x) const {
mat res;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k)
res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * x.a[k][j] % mod) % mod;
return res;
}
void Swap() { swap(a[0][0], a[1][1]), swap(a[0][1], a[1][0]); }
};
struct Segment_Tree {
mat t[N*4]; int tag[N*4];
void pushup(int p) { t[p] = t[ls(p)] * t[rs(p)]; }
void pushdown(int p) { if (!tag[p]) return; t[ls(p)].Swap(), tag[ls(p)] ^= 1, t[rs(p)].Swap(), tag[rs(p)] ^= 1, tag[p] = 0; }
void build(int p, int l, int r) {
if (l == r) {
if (s[l] == 'A') t[p] = mat(1, 0, 1, 1);
else t[p] = mat(1, 1, 0, 1);
return;
}
int mid = l + r >> 1;
build(ls(p), l, mid), build(rs(p), mid + 1, r);
pushup(p);
}
void change(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[p].Swap(), tag[p] ^= 1, void();
pushdown(p);
int mid = l + r >> 1;
if (x <= mid) change(ls(p), l, mid, x, y);
if (y > mid) change(rs(p), mid + 1, r, x, y);
pushup(p);
}
mat query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[p];
pushdown(p);
int mid = l + r >> 1; mat res = mat(1, 0, 0, 1);
if (x <= mid) res = res * query(ls(p), l, mid, x, y);
if (y > mid) res = res * query(rs(p), mid + 1, r, x, y);
return res;
}
} sTr;
int main() {
scanf("%d%d%s", &n, &Q, s + 1);
sTr.build(1, 1, n);
while (Q--) {
int ty, l, r, a, b; scanf("%d%d%d", &ty, &l, &r);
if (ty == 1) sTr.change(1, 1, n, l, r);
else {
scanf("%d%d", &a, &b);
mat tmp = sTr.query(1, 1, n, l, r);
int A = (1ll * a * tmp.a[0][0] % mod + 1ll * b * tmp.a[1][0] % mod) % mod;
int B = (1ll * a * tmp.a[0][1] % mod + 1ll * b * tmp.a[1][1] % mod) % mod;
printf("%d %d\n", A, B);
}
}
return 0;
}