线段维护矩阵乘法
<pre><code>#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e5+5;
struct Max{
ll a[5][5];
Max operator*(const Max &m){
Max M;
for(int i = 1; i <= 2; i++){
for(int j = 1; j <= 2; j++){
ll sum = 0;
for(int k = 1; k <= 2; k++){
sum = (sum + this->a[i][k] * m.a[k][j] % mod) % mod;
}
M.a[i][j] = sum;
}
}
return M;
}
Max(){
this->a[1][1] = this->a[2][2] = 1;
this->a[1][2] = this->a[2][1] = 0;
}
};
struct Node{
Max sum;
int l;
int r;
};
int n, m;
Node tree[4*maxn+5];
int cnt = 1;
void build(Node *tree, int now, int l, int r){
tree[now].l = l;
tree[now].r = r;
if(tree[now].l == tree[now].r){
//处理矩阵
return;
}
int mid = (l + r) >> 1;
build(tree, 2*now, l, mid);
build(tree, 2*now+1, mid+1, r);
tree[now].sum = tree[2*now].sum * tree[2*now+1].sum;
return;
}
void updata(Node *tree, int now, int z, ll k, ll b){
if(tree[now].l == tree[now].r){
//处理矩阵
return;
}
int mid = (tree[now].l + tree[now].r) >> 1;
if(z <= mid) updata(tree, 2*now, z, k, b);
else updata(tree, 2*now+1, z, k, b);
tree[now].sum = tree[2*now].sum * tree[2*now+1].sum;
return;
}
Max query(Node *tree, int now, int l, int r){
if(tree[now].l >= l && tree[now].r <= r) return tree[now].sum;
int mid = (tree[now].l + tree[now].r) >> 1;
return (l <= mid? query(tree, 2*now, l, r): Max()) * (r > mid? query(tree, 2*now+1, l, r): Max());
}</code></pre>