線段樹維護矩陣乘法
- 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; }
