题目大意
给你一个序列(a_1, a_2, ..., a_n). 我们令函数(f(n))表示斐波那契数列第(n)项的值. 总共(m)个操作, 分为以下两种:
- 将(x in [L, R])中的所有(a_x)加上一个数(k);
- 询问(sum_{x in [L, R]}f(a_x))
(n le 10^5)
(m le 10^5)
Solution
我们靠考虑斐波那契数列的转移矩阵:
[[f_{a + b - 1} f_{a + b}] = [f_{a - 1} f_a] left[ egin{array}{} 0 1 \ 1 1 end{array}
ight]^b
]
同时我们发现若干个斐波那契数之和也满足这个关系.
因此我们用线段树维护每个区间的(sum_{L le i le R} f(a_i))以及(sum_{L le i le R} f(a_{i - 1})), 区间修改查询即可.
注意作为常数优化, 我们要预处理出转移矩阵的(2^n)次幂. 否则会TLE.
话说拿这种小技巧, 把正确复杂度的代码卡到30分, 是不是也太丧心病狂了!!!
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
namespace Zeonfai
{
inline long long getInt()
{
long long a = 0, sgn = 1; char c;
while(! isdigit(c = getchar())) if(c == '0') sgn *= -1;
while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
const long long N = (long long)1e5, MOD = (long long)1e9 + 7;
long long n;
struct matrix
{
long long a[2][2];
inline matrix operator *(const matrix &A)
{
matrix res; memset(res.a, 0, sizeof(res.a));
for(long long i = 0; i < 2; ++ i) for(long long j = 0; j < 2; ++ j) for(long long k = 0; k < 2; ++ k)
res.a[i][j] = (res.a[i][j] + (long long)a[i][k] * A.a[k][j] % MOD) % MOD;
return res;
}
}trans, ptt[64];
inline matrix power(long long x)
{
matrix res; memset(res.a, 0, sizeof(res.a)); res.a[0][0] = res.a[1][1] = 1;
if(x < 0) return res;
long long p = 0;
for(; x; x >>= 1, ++ p)
if(x & 1) res = res * ptt[p];
return res;
}
struct segmentTree
{
struct node
{
long long cur, lst;
long long tg; // 注意到tg的值叠加后可能超过Long long
inline node() {cur = 0; lst = 1; tg = 0;}
}nd[N << 2];
inline void pushDown(long long _u)
{
long long x = nd[_u].tg; long long u = _u << 1;
matrix res = power(x);
long long a = ((long long)nd[u].lst * res.a[0][0] % MOD + (long long)nd[u].cur * res.a[1][0] % MOD) % MOD,
b = ((long long)nd[u].lst * res.a[0][1] % MOD + (long long)nd[u].cur * res.a[1][1] % MOD) % MOD;
nd[u].lst = a; nd[u].cur = b;
nd[u].tg += x;
u = _u << 1 | 1;
a = ((long long)nd[u].lst * res.a[0][0] % MOD + (long long)nd[u].cur * res.a[1][0] % MOD) % MOD;
b = ((long long)nd[u].lst * res.a[0][1] % MOD + (long long)nd[u].cur * res.a[1][1] % MOD) % MOD;
nd[u].lst = a; nd[u].cur = b;
nd[u].tg += x;
nd[_u].tg = 0;
}
void modify(long long u, long long curL, long long curR, long long L, long long R, long long x)
{
if(curL >= L && curR <= R)
{
nd[u].tg += x;
matrix res = power(x);
long long a = ((long long)nd[u].lst * res.a[0][0] % MOD + (long long)nd[u].cur * res.a[1][0] % MOD) % MOD,
b = ((long long)nd[u].lst * res.a[0][1] % MOD + (long long)nd[u].cur * res.a[1][1] % MOD) % MOD;
nd[u].lst = a; nd[u].cur = b;
return;
}
pushDown(u);
long long mid = curL + curR >> 1;
if(L <= mid) modify(u << 1, curL, mid, L, R, x);
if(R > mid) modify(u << 1 | 1, mid + 1, curR, L, R, x);
nd[u].cur = (nd[u << 1].cur + nd[u << 1 | 1].cur) % MOD;
nd[u].lst = (nd[u << 1].lst + nd[u << 1 | 1].lst) % MOD;
}
inline void modify(long long L, long long R, long long x) {modify(1, 1, n, L, R, x);}
long long query(long long u, long long curL, long long curR, long long L, long long R)
{
if(curL >= L && curR <= R) return nd[u].cur;
pushDown(u);
long long mid = curL + curR >> 1, res = 0;
if(L <= mid) res = query(u << 1, curL, mid, L, R);
if(R > mid) res = (res + query(u << 1 | 1, mid + 1, curR, L, R)) % MOD;
return res;
}
inline long long query(long long L, long long R) {return query(1, 1, n, L, R);}
}seg;
int main()
{
#ifndef ONLINE_JUDGE
freopen("fibonacci.in", "r", stdin);
freopen("_fibonacci.out", "w", stdout);
#endif
using namespace Zeonfai;
trans.a[0][0] = 0; trans.a[0][1] = trans.a[1][0] = trans.a[1][1] = 1;
ptt[0] = trans;
for(long long i = 1; i < 64; ++ i) ptt[i] = ptt[i - 1] * ptt[i - 1];
n = getInt(); long long m = getInt();
for(long long i = 1; i <= n; ++ i) seg.modify(i, i, getInt());
for(long long i = 0; i < m; ++ i)
{
long long opt = getInt(), L = getInt(), R = getInt();
if(opt == 1)
{
long long x = getInt();
seg.modify(L, R, x);
}
else if(opt == 2) printf("%d
", seg.query(L, R));
}
}