线段树维护矩阵乘法
- 2019 年 11 月 25 日
- 筆記
线段树维护矩阵乘法
2019-2020 ICPC, Asia Jakarta Regional Contest
K Addition Robot
题目
Adding two numbers several times is a time-consuming task, so you want to build a robot. The robot should have a string of characters on its memory that represents addition instructions. Each character of the string, , is either or.
You want to be able to give commands to the robot, each command is either of the following types:
- 1 . The robot should toggle all the characters of where . Toggling a character means changing it to if it was previously , or changing it to if it was previously .
- 2 . The robot should call and return two integers as defined in the following pseudocode:
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)
You want to implement the robot's expected behavior.
Input
Input begins with a line containing two integers: () representing the number of characters in the robot's memory and the number of commands, respectively. The next line contains a string containing characters (each either or ) representing the initial string in the robot's memory. The next lines each contains a command of the following types.
- 1
- 2
There is at least one command of the second type.
output
For each command of the second type in the same order as input, output in a line two integers (separated by a single space), the value of and returned by , respectively. As this output can be large, you need to modulo the output by .
Example
input
5 3 ABAAA 2 1 5 1 1 1 3 5 2 2 5 0 1000000000
output
11 3 0 1000000000
翻译
给一个长度为的,字符串，给出次询问。
- 操作1 输入， 将区间，的变为，变为；
- 操作2 输入, , ，，在进行遍历，若遇到则，若遇到 则,输出最后，的值
如样例第一个询问2 1 5 1 1则在区间[1，5]上遍历，初始值，。
第一个遇到，所以，；
第二个遇到，所以，；
第三个遇到，所以 ，；
第四个遇到，所以，；
第五个遇到，所以，；
输出答案，；
题解
先不考虑操作1
注意到两个矩阵
这两个操作像不像遇到和时候的两种操作？至于为什么要这样构造矩阵，只能说这样构造可以解决，可以当成一种套路，这种线性的递推变换都可以通过构造一个转移矩阵得到解决。
然后对于一个区间， 遇到我们就乘矩阵(1)，遇到B我们就乘一个矩阵(2)对于样例[1，5]区间来说
而矩阵是满足结合律的可以将即
所以我们需要做的只是求出某个询问区间[L，R]的矩阵的积，这显然是可以用线段树做到的。
再考虑操作1，将区间中的变成，变成
之前讲到用线段树去查询区间的矩阵积，这里带了一种修改，但是一个区间，最多只会有两种情况，要么被交换了和要么没有被交换，所以在用线段树维护的时候将两个情况都维护一下，如果要进行交换，则直接交换维护的两个值即可。因为是区间修改，所以用打一下标记。
最近的一场关于印尼Regional镜像赛，codefoces上可补题
最后推荐看懂的同学自己写一下，因为太菜所以觉得细节还是蛮多的hhhh。
代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define mp make_pair const int maxn = 1e5+5; const int MOD = 1e9+7; #define mod(x) x % MOD #define INF 0x3f3f3f3f char a[maxn]; struct mat{ ll m[3][3]; }unit; mat mul(mat a, mat b, int sz) { mat x; for(int i = 0;i < sz;i++) { for(int j = 0;j < sz;j++) { ll res = 0; for(int k = 0;k < sz;k++) { res += a.m[i][k] * b.m[k][j]; res = mod(res); } x.m[i][j] = mod(res); } } return x; } struct node { int l, r; int mid() { return (l + r) / 2; } mat ans, rans; int lazy; } tree[maxn << 2]; void pushUp(int rt) { tree[rt].ans = mul(tree[rt << 1].ans, tree[rt << 1 | 1].ans, 2); tree[rt].rans = mul(tree[rt << 1].rans, tree[rt << 1 | 1].rans, 2); } void pushDown(int rt) { if(tree[rt].lazy) { swap(tree[rt << 1].ans, tree[rt << 1].rans); swap(tree[rt << 1 | 1].ans, tree[rt << 1 | 1].rans); tree[rt << 1].lazy ^= 1; tree[rt << 1 | 1].lazy ^= 1; tree[rt].lazy = 0; } } void build(int rt, int l, int r) { tree[rt].l = l, tree[rt].r = r; tree[rt].lazy = 0; if(l == r){ if(a[l] == 'A') { tree[rt].ans.m[0][0] = 1, tree[rt].ans.m[0][1] = 0; tree[rt].ans.m[1][0] = 1, tree[rt].ans.m[1][1] = 1; tree[rt].rans.m[0][0] = 1, tree[rt].rans.m[0][1] = 1; tree[rt].rans.m[1][0] = 0, tree[rt].rans.m[1][1] = 1; } if(a[l] == 'B') { tree[rt].ans.m[0][0] = 1, tree[rt].ans.m[0][1] = 1; tree[rt].ans.m[1][0] = 0, tree[rt].ans.m[1][1] = 1; tree[rt].rans.m[0][0] = 1, tree[rt].rans.m[0][1] = 0; tree[rt].rans.m[1][0] = 1, tree[rt].rans.m[1][1] = 1; } return; } int m = tree[rt].mid(); build(rt << 1, l, m); build(rt << 1 | 1, m + 1, r); pushUp(rt); } void update(int rt, int l, int r) { if(tree[rt].l >= l && tree[rt].r <= r) { tree[rt].lazy ^= 1; swap(tree[rt].ans, tree[rt].rans); return; } pushDown(rt); int m = tree[rt].mid(); if(r <= m) update(rt << 1, l, r); else if(l > m) update(rt << 1 | 1, l, r); else { update(rt << 1, l, m); update(rt << 1 | 1, m + 1, r); } pushUp(rt); } mat query(int rt, int l, int r) { if(tree[rt].l >= l && tree[rt].r <= r) { return tree[rt].ans; } pushDown(rt); int m = tree[rt].mid(); mat res; if(r <= m) { res = query(rt << 1, l, r); } else if(l > m) { res = query(rt << 1 | 1, l, r); } else { res = query(rt << 1, l, m); res = mul(res, query(rt << 1 | 1, m + 1, r), 2); } pushUp(rt); return res; } int main(){ int n = 0, q = 0; scanf("%d %d", &n, &q); scanf("%s", a + 1); build(1, 1, n); mat A, B; B.m[0][0] = 1, B.m[0][1] = 1; B.m[1][0] = 0, B.m[1][1] = 1; A.m[0][0] = 1, A.m[0][1] = 0; A.m[1][0] = 1, A.m[1][1] = 1; while(q--) { int k = 0; scanf("%d", &k); if(k == 1) { int l, r; scanf("%d %d", &l, &r); update(1, l, r); } else { int l, r; ll a, b; scanf("%d %d %lld %lld", &l, &r, &a, &b); mat C; C.m[0][0] = a, C.m[0][1] = b; mat tmp = query(1, l, r); C = mul(C, tmp, 2); printf("%lld %lldn", mod(C.m[0][0]), mod(C.m[0][1]) ); } } return 0; }
