题意
定义斐波那契数列（Fibonacci sequence) $F\left(x\right) = F\left(x - 1\right) + F\left(x - 2\right)$，特别 $F\left(1\right) = F\left(2\right) = 1$。
给定长度为 $n$ 的数组 $a$，维护 $m$ 个操作，对于每个操作：
1 l r表示对于 $l \leq i \leq r$，将 $a_i$ 加上 $f_{i - l + 1}$，即对 $\left[l, r\right]$ 加上从首相开始的斐波那契数列。2 l r表示求 $\displaystyle \sum\limits_{i = l}^r a_i$ 对 $10^9 + 9$ 取模。
$1 \leq n, m \leq 3 \times 10^5, 1 \leq a_i \leq 10^9$。
题解
做法 1
简单的根号定期重构做法。
首先我们可以在每次修改操作时，使用 $\mathcal O\left(n\right)$ 的时间应用到 $a$ 数组，而每次询问操作可以 $\mathcal O\left(1\right)$ 完成。
还可以在每次询问操作时，花费 $\mathcal O\left(n\right)$ 的时间遍历之前所有的修改，而每次修改操作时只需要 $\mathcal O\left(1\right)$ 记录一下即可。
但是我们可以根号分治。
于是两种操作的时间复杂度就都是根号级别的了。
// Please submit with C++20!
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <list>
#include <map>
#include <ranges>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define sc(n) sv::iota(1) | sv::take(n)
using namespace std;
using tp = long long;
namespace sv = std::ranges::views;
constexpr tp _MOD_ = 1e9 + 9;
tp n;
vector<tp> tar, tmp, fib, fs;
vector<pair<tp, tp>> rm;
tp mod(tp v) {
if (v < 0) {
return v + _MOD_;
} else if (v >= _MOD_) {
v -= _MOD_;
} else if (v >= _MOD_) {
v -= _MOD_;
}
return v;
}
void maintain() {
auto&& [a, b] = make_pair(tp(0), tp(0));
vector<list<tp>> q(n + 1), p(n + 1);
for (auto&& i : sv::iota(0) | sv::take(rm.size())) {
q[rm[i].first].push_back(i);
p[rm[i].second].push_back(i);
}
for (auto&& i : sc(n)) {
tp c = a + b;
a = b;
b = c;
tmp[i] = mod(tmp[i] + b);
b = mod(b + q[i].size());
tmp[i] = mod(tmp[i] + q[i].size());
for (auto&& i : p[i]) {
a = mod(a - fib[rm[i].second - rm[i].first]);
b = mod(b - fib[rm[i].second - rm[i].first + 1]);
}
tar[i] = mod(tar[i - 1] + tmp[i]);
}
for (auto&& [i, j] : rm) {
q[i].clear();
p[j].clear();
}
rm.clear();
}
signed main() {
bool c = 0;
tp m, gmt;
scanf("%lld%lld", &n, &m);
tar = tmp = fib = fs = vector(n + 1, tp(0));
tie(fib[1], fib[2], fs[1], fs[2], gmt) = make_tuple(1, 1, 1, 2, tp(sqrt(m)));
for (tp i = 3; i <= n; ++i) {
fs[i] = mod(fs[i - 1] + (fib[i] = mod(fib[i - 1] + fib[i - 2])));
}
for (tp i = 1; i <= n; ++i) {
scanf("%lld", &tmp[i]);
tar[i] = mod(tar[i - 1] + tmp[i]);
}
for (tp op, l, r; m--;) {
scanf("%lld%lld%lld", &op, &l, &r);
if (op == 1) {
if (rm.emplace_back(l, r); rm.size() == gmt && c) {
maintain();
rm.reserve(gmt);
}
} else {
tp sum = 0;
c = 1;
for (auto&& [_l, _r] : rm) {
if (tp __l = max(l, _l), __r = min(r, _r); __l <= __r) {
sum = mod(sum + fs[__r - _l + 1] - fs[__l - _l]);
}
}
printf("%lld\n", mod(sum + tar[r] - tar[l - 1]));
}
}
return 0;
}做法 2
思路简单的广义斐波那契维护做法。
我们知道，两个广义斐波那契相加的和还是广义斐波那契。
因此，我们只需要对于每个区间维护广义斐波那契的表示方式（即 $F\left(1\right)$ 与 $F\left(2\right)$），还有区间和。
时间复杂度 $\Theta\left(n \log n\right)$。
代码稍后会补上来。
做法 3
思路简单的斐波那契通项维护做法。
$$F\left(x\right) = \frac1{\sqrt5}\left[\left(\frac{1 + \sqrt5}2\right)^x - \left(\frac{1 - \sqrt5}2\right)^x\right]$$
然后可以直接转化为线段树维护区间加等比数列，直接套等比数列求和公式即可。
$5$ 在模 $10^9 + 9$ 下有二次剩余，当然也可以扩域。
时间复杂度 $\Theta\left(n \log n\right)$。
代码稍后会补上来。