线段树/维护转移矩阵（中石油组队赛 K: Addition Robot）"/>
线段树/维护转移矩阵（中石油组队赛 K: Addition Robot）
显然是个线段树，如果初始值为x，y。则最后答案显然是 x ′ = a 1 x + b 1 y , y ′ = a 2 x + b 2 y x'=a_1x+b_1y, \ \ y'=a_2x+b_2y x′=a1x+b1y, y′=a2x+b2y我们就是用线段树维护这个系数。题目是关于状态累加的，显然可以用矩阵来维护转移状态。而矩阵乘是满足结合律的，显然可以用线段树维护（其实我们队一开始想的是分块，可是一拍脑门，既然都可以结合合并了，那还用个pi的分块）。这里我们如果将初始x，y写入矩阵：
a n s = ( x y 0 0 ) ans=\begin{pmatrix} x & y \\ 0 & 0 \end{pmatrix} \quad ans=(x0y0)
而对于字符’A‘有转移矩阵：
a = ( 1 0 1 1 ) a=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \quad a=(1101)
同理对于’B‘：
b = ( 1 1 0 1 ) b=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \quad b=(1011)
显然，例如对于序列”AABBAB“，最终目标矩阵是：
a n s ′ = a n s ∗ a ∗ a ∗ b ∗ b ∗ a ∗ b ans'=ans*a*a*b*b*a*b ans′=ans∗a∗a∗b∗b∗a∗b
其中 x ′ = a n s 0 , 0 ′ y ′ = a n s 0 , 1 ′ x'=ans'_{0,0}\ \ y'=ans'_{0,1} x′=ans0,0′ y′=ans0,1′
对于反转，我们对于每个区间，事先计算反转前后的矩阵。然后进行laz标记，决定用哪一个矩阵。即可。
ps.好像有大佬是直接维护的系数，和矩阵其实是一样的。（但是常数小。QAQ菜鸡流泪）
下面是ac代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include <map>
#include <queue>
#include <set>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <array>
#include <cctype>
#include <time.h>#pragma GCC optimize(2)void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);}
void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); }
void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; }#define ll long long
#define ull unsigned ll
#define _min(x, y) ((x)>(y)?(y):(x))
#define _max(x, y) ((x)>(y)?(x):(y))
#define max3(x, y, z) ( max( (x), max( (y), (z) ) ) )
#define min3(x, y, z) ( min( (x), min( (y), (z) ) ) )
#define pr(x, y) (make_pair((x), (y)))
#define pb(x) push_back(x);
using namespace std;const int N = 1e5+5;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;struct M
{ll a[2][2];friend M operator * (const M & a, const M b){M c;for (int i = 0; i < 2; i++){for (int j = 0; j < 2; j++){c.a[i][j] = 0;for (int k = 0; k < 2; k++)c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;}}return c;}M(){};M(int flag) {if (flag == 0) a[0][0] = a[1][0] = a[1][1] = 1, a[0][1] = 0;else a[0][0] = a[0][1] = a[1][1] = 1, a[1][0] = 0;}M(int _a, int _b){a[0][0] = _a, a[0][1] = _b;a[1][0] = a[1][1] = 0;}
}a, b, ans;
struct Node
{int l, r;int laz;M ans1, ans2;
} tr[N<<2];
char su[N];
inline void pushup(int p)
{tr[p].ans1 = tr[p<<1].ans1 * tr[p<<1|1].ans1;tr[p].ans2 = tr[p<<1].ans2 * tr[p<<1|1].ans2;
}
inline void spread(int p)
{if (tr[p].laz == 1){tr[p].laz = 0;tr[p<<1].laz ^= 1; tr[p<<1|1].laz ^= 1;swap(tr[p<<1].ans1, tr[p<<1].ans2);swap(tr[p<<1|1].ans1, tr[p<<1|1].ans2);}
}
void build(int p, int l, int r)
{tr[p].l = l; tr[p].r = r;tr[p].laz = 0;if (l == r) {if (su[l] == 'A') tr[p].ans1 = a, tr[p].ans2 = b;else tr[p].ans2 = a, tr[p].ans1= b;return;}int mid = (l + r) >> 1;build(p<<1, l, mid);build(p<<1|1, mid+1, r);pushup(p);
}
void change(int p, int l, int r)
{//cout << p << " " << tr[p].l << " " << tr[p].r <<endl;if (l <= tr[p].l && tr[p].r <= r) {tr[p].laz ^= 1;swap(tr[p].ans1, tr[p].ans2);return;}spread(p);int mid = (tr[p].l + tr[p].r) >> 1;if (l <= mid) change(p<<1, l, r);if (r > mid) change(p<<1|1, l, r);pushup(p);
}
void ask(int p, int l, int r)
{if (l <= tr[p].l && tr[p].r <= r){ans = ans * tr[p].ans1;return;}spread(p);int mid = (tr[p].l + tr[p].r) >> 1;if(l <= mid) ask(p<<1, l, r);if (r > mid) ask(p<<1|1, l, r);
}
void printm(M a)
{printf("---------------------\n");for (int i = 0; i < 2; i++){for (int j = 0; j < 2; j++)cout << a.a[i][j] << " ";cout << endl;}
}
int main()
{a = M(0); b = M(1);int n, m; scanf("%d%d", &n, &m);scanf("%s", su+1);build(1, 1, n);while(m--){int op, l, r; scanf("%d%d%d", &op, &l, &r);if (op == 1){change(1, l, r);}else{int x, y; scanf("%d%d", &x, &y);ans = M(x, y);//printm(ans);ask(1, l, r);//printm(ans);printf("%lld %lld\n", ans.a[0][0], ans.a[0][1]);}}return 0;
}
更多推荐
线段树/维护转移矩阵（中石油组队赛 K: Addition Robot）
发布评论