cf-Sasha and Array

题目链接 http://codeforces.com/problemset/problem/719/E

解题思路

矩阵上的线段树。

因为矩阵有分配律（A+B）C = AC + BC，所以计算总和时直接把增量矩阵乘上去就行了。用矩阵快速幂。

fib的计算尽量拉到主函数计算。

代码

#include<stdio.h>
#include<string.h>#define MAX_SIZE 100010
const int MOD_NUM = 1e9 + 7;
typedef long long ll;
struct mat {mat() {}mat(int a, int b, int c, int d){ ans[0][0] = a; ans[0][1] = b; ans[1][0] = c; ans[1][1] = d; } int ans[2][2];bool JudgeOne(){for(int i=0; i<2; i++)for(int j=0; j<2; j++)if(i == j && ans[i][j] != 1 || i != j && ans[i][j] != 0)return false;return true;}void SetOne(){for(int i=0; i<2; i++)for(int j=0; j<2; j++)ans[i][j] = (i == j) ? 1 : 0;}mat operator *(const mat &b)const{mat c(0,0,0,0);for(int k=0; k<2; k++)for(int i=0; i<2; i++)for(int j=0; j<2; j++)c.ans[i][j] = (c.ans[i][j] + (ll)ans[i][k] * b.ans[k][j]) % MOD_NUM;return c;}mat operator +(const mat &b)const{mat c;for(int i=0; i<2; i++)for(int j=0; j<2; j++)c.ans[i][j] = (ans[i][j] + b.ans[i][j]) % MOD_NUM; return c;}
};
struct node {mat sum; mat tempt;    
}tree[4*MAX_SIZE];
mat a[MAX_SIZE];
mat temp;
mat cal_fib(int x)
{mat c; mat t(0,1,1,1);c.SetOne();while(x) {if(x & 1) c = c * t;t = t * t;x  = x >> 1;}return c;
}
void build(int l, int r, int root)
{tree[root].tempt.SetOne();if(l == r) {tree[root].sum = a[l];return ;}int mid = (l + r) / 2;build(l, mid, root*2);build(mid+1, r, root*2+1);tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;
}
void down(int root)
{tree[root*2].sum = tree[root*2].sum * tree[root].tempt;tree[root*2].tempt = tree[root*2].tempt * tree[root].tempt;tree[root*2+1].sum = tree[root*2+1].sum * tree[root].tempt;tree[root*2+1].tempt = tree[root*2+1].tempt * tree[root].tempt;tree[root].tempt.SetOne();
}
void query_1(int l, int r, int L, int R, int root, mat value)
{if(L == l && r == R) {tree[root].tempt = tree[root].tempt * value;tree[root].sum = tree[root].sum * value;return ;}if(!tree[root].tempt.JudgeOne()) {down(root);}int mid = (L + R) / 2;if(r <= mid) query_1(l, r, L, mid, root*2, value);else if(l > mid) query_1(l, r, mid+1, R, root*2+1, value);else {query_1(l, mid, L, mid, root*2, value);query_1(mid+1, r, mid+1, R, root*2+1, value);}tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;
}
int query_2(int l, int r, int L, int R, int root)
{if(L == l && r == R) {return tree[root].sum.ans[0][1];}if(!tree[root].tempt.JudgeOne()) {down(root);}int ret = 0;int mid = (L + R) / 2;if(r <= mid) ret = query_2(l, r, L, mid, root*2);else if(l > mid) ret = query_2(l, r, mid+1, R, root*2+1);else {ret = query_2(l, mid, L, mid, root*2) + query_2(mid+1, r, mid+1, R, root*2+1) % MOD_NUM;}return ret % MOD_NUM;
}
int main()
{int n, m, d;scanf("%d%d", &n, &m);for(int i=1; i<=n; i++) {mat base(0, 1, 1, 1);scanf("%d", &d); a[i] = cal_fib(d);}build(1, n, 1);for(int i=0; i<m; i++) {int type, l, r, x;scanf("%d", &type);if(type == 1) {mat base(0, 1, 1, 1);scanf("%d%d%d", &l, &r, &x);temp = cal_fib(x);query_1(l, r, 1, n, 1, temp);}else {scanf("%d%d", &l, &r);printf("%d\n", query_2(l, r, 1, n, 1));}}return 0;
}