codeforces 1252K 线段树维护矩阵

分析

对于操作一，相当于翻转，我们可以用异或去处理这个标记 对于操作二，即查询$[L,R]$这个区间的结果 对于初始值$a,b$，我们有$x1\ast a+y1\ast b,x2\ast a+y2\ast b$，即$A,B$ 其实这个操作就是一个矩阵的变化 我们维护一个$2\times 2$的矩阵 $$\left\{\begin{array}{cc}a& b\end{array}\right\}\ast \left\{\begin{array}{cc}1& 0\\ 1& 1\end{array}\right\}=\left\{\begin{array}{cc}a+b& b\end{array}\right\}$$

$$\left\{\begin{array}{cc}a& b\end{array}\right\}\ast \left\{\begin{array}{cc}1& 1\\ 0& 1\end{array}\right\}=\left\{\begin{array}{cc}a& a+b\end{array}\right\}$$

我们发现题目所给的查询操作可以看成维护区间矩阵的乘积 所以我们用线段树去维护区间矩阵积

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; template <typename T> void out(T x) { cout << x << endl; } ll fast_pow(ll a, ll b, ll p) {ll c = 1; while(b) { if(b & 1) c = c * a % p; a = a * a % p; b >>= 1;} return c;} ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) {x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, y, x); y-= a / b * x; return gcd; } const ll N = 1e5 + 10; const ll mod = 1e9 + 7; struct matrix { ll mx[2][2]; matrix(ll a = 1, ll b = 0, ll c = 0, ll d = 1) { mx[0][0] = a; mx[0][1] = b; mx[1][0] = c; mx[1][1] = d; } matrix operator * (const matrix b) const { matrix c = matrix(0, 0, 0, 0); for(ll i = 0; i < 2; i ++) for(ll j = 0; j < 2; j ++) for(ll k = 0; k < 2; k ++) c.mx[i][j] = (c.mx[i][j] + mx[i][k] * b.mx[k][j] % mod) % mod; return c; } void mat_swap() { swap(mx[0][0], mx[1][1]); swap(mx[0][1], mx[1][0]); } void print() { cout << mx[0][0] << " " << mx[0][1] << endl; cout << mx[1][0] << " " << mx[1][1] << endl; } }mat[N << 3]; ll lazy[N << 3]; ll n, q; char str[N]; void push_up(ll rt) { mat[rt] = mat[rt << 1] * mat[rt << 1 | 1]; } void push_down(ll rt) { if(lazy[rt]) { mat[rt].mat_swap(); lazy[rt << 1] ^= 1; lazy[rt << 1 | 1] ^= 1; lazy[rt] = 0; } } void build(ll l, ll r, ll rt) { if(l == r) { if(str[l] == 'A') mat[rt] = matrix(1, 0, 1, 1); else if(str[l] == 'B') mat[rt] = matrix(1, 1, 0, 1); return ; } ll mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1); push_up(rt); } void update(ll l, ll r, ll L, ll R, ll rt) { push_down(rt); if(l > R || r < L) return ; if(L <= l && r <= R) { lazy[rt] ^= 1; push_down(rt); return ; } ll mid = (l + r) >> 1; update(l, mid, L, R, rt << 1); update(mid + 1, r, L, R, rt << 1 | 1); push_up(rt); } matrix query(ll l, ll r, ll L, ll R, ll rt) { push_down(rt); if(l > R || r < L) return matrix(); if(L <= l && r <= R) return mat[rt]; ll mid = (l + r) >> 1; matrix m1 = query(l, mid, L, R, rt << 1); matrix m2 = query(mid + 1, r, L, R, rt << 1 | 1); return m1 * m2; } int main() { ios::sync_with_stdio(false); cin >> n >> q; cin >> (str + 1); build(1, n, 1); while(q --) { ll d; cin >> d; if(d == 1) { ll l, r; cin >> l >> r; update(1, n, l, r, 1); } else { ll l, r, a, b; cin >> l >> r >> a >> b; matrix mm = query(1, n, l, r, 1); ll A = (a * mm.mx[0][0] % mod + b * mm.mx[1][0] % mod) % mod; ll B = (a * mm.mx[0][1] % mod + b * mm.mx[1][1] % mod) % mod; cout << A << " " << B << endl; } } }