线段树维护矩阵乘法
线段树维护矩阵乘法
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 1000000000output
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 %lld\n", mod(C.m[0][0]), mod(C.m[0][1]) );
}
}
return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
