CF446C DZY Loves Fibonacci Numbers 题解和加强

标签：CF446C int 题解 sum sf2 sf1 Fibonacci tg 那契

简要题意

https://www.luogu.com.cn/problem/CF446C

给定一个长度为 \(n\) 的序列 \(A\)，要求支持两种操作：1 给定区间 \((l, r)\) 对这个区间内的每个数，依次加斐波那契数列的前 \(r - l + 1\) 项；2 给定区间求和。
数据范围：\(1\le n \le 3\times10^5, 1 \le q \le 3\times 10^5\)。

加强：给定区间求平方和。

原题思路

斐波那契数列的差分、前缀和还是斐波那契数列，和区间加一次函数、二次函数等有本质区别，经典的差分、前缀和等处理以后数据结构维护的简单思路是行不通的。必须另辟蹊径。

根据斐波那契数列的递推式可以得到它的一个性质：两个斐波那契数列错开一位，相减以后得到的也是一个斐波那契数列，并且这个斐波那契数列相对于原先两个，又向前移动一位，如下所示：

\[\begin{aligned} &F_1: \{1, 1, 2, 3, 5, 8, 13,\cdots\}\\ &F_2: \{0, 1, 1, 2, 3, 5, 8,\cdots\}\\ &F_3: \{1, 0, 1, 1, 2, 3, 5,\cdots\}\\ &F_4: \{-1, 1, 0, 1, 1, 2, 3,\cdots\}\\ \end{aligned} \]

注意到 \(\forall i > 2, F_{i, j} = F_{i - 2, j} - F_{i - 1, j}\)，于是所有的 \(F\) 的每一行都可以表示为 \(F_1, F_2\) 的线性组合，且系数可以在 \(\Theta(n)\) 时间递推预处理得到。

这些数组可以帮助我们进行区间加的操作。首先考虑另一个经典模型：给定序列 \(A, B\)，\(B\) 始终不变，要求支持一种操作给定 \(l, r\)，使 \(\forall l\le i\le r, A_i \leftarrow A_i + kB_i\)，维护 \(A\) 的区间和。这直接在线段树上令 tag 是 \(B\) 的系数即可，对于下推标记和区间更新，通过预处理 \(B\) 的前缀和即可做到。如果不止有一个数组，也是一个道理，因为两个数组互不影响。

时间/空间复杂度 \(\Theta(n \log n)/\Theta(n)\)。

原题代码

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

const int N = 300005, P = 1000000009;

int sf1[N], sf2[N];

struct SegTree
{
	int sum[N << 2];
	pair<int, int> tg[N << 2];

	void update(int p)
	{
		sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % P;
	}

	void pushdown(int p, int cl, int cr)
	{
		int cm = (cl + cr) >> 1;
		LL t1 = tg[p].first, t2 = tg[p].second;
		tg[p] = {0, 0};
		sum[p * 2] = (sum[p * 2] + t1 * (sf1[cm] - sf1[cl - 1] + P)) % P;
		sum[p * 2] = (sum[p * 2] + t2 * (sf2[cm] - sf2[cl - 1] + P)) % P;
		sum[p * 2 + 1] = (sum[p * 2 + 1] + t1 * (sf1[cr] - sf1[cm] + P)) % P;
		sum[p * 2 + 1] = (sum[p * 2 + 1] + t2 * (sf2[cr] - sf2[cm] + P)) % P;
		(tg[p * 2].first += t1) %= P;
		(tg[p * 2].second += t2) %= P;
		(tg[p * 2 + 1].first += t1) %= P;
		(tg[p * 2 + 1].second += t2) %= P;
	}

	void add(int p, int cl, int cr, int l, int r, LL x1, LL x2)
	{
		if (cl >= l && cr <= r)
		{
			sum[p] = (sum[p] + x1 * (sf1[cr] - sf1[cl - 1] + P)
				+ x2 * (sf2[cr] - sf2[cl - 1] + P)) % P;
			(tg[p].first += x1) %= P;
			(tg[p].second += x2) %= P;
			return;
		}
		pushdown(p, cl, cr);
		int cm = (cl + cr) >> 1;
		if (l <= cm)
		{
			add(p * 2, cl, cm, l, r, x1, x2);
		}
		if (r > cm)
		{
			add(p * 2 + 1, cm + 1, cr, l, r, x1, x2);
		}
		update(p);
	}

	LL get_sum(int p, int cl, int cr, int l, int r)
	{
		if (cl >= l && cr <= r)
		{
			return sum[p];
		}
		pushdown(p, cl, cr);
		int cm = (cl + cr) >> 1;
		LL ret = 0;
		if (l <= cm)
		{
			ret += get_sum(p * 2, cl, cm, l, r);
		}
		if (r > cm)
		{
			ret += get_sum(p * 2 + 1, cm + 1, cr, l, r);
		}
		return ret % P;
	}
} segt;

int n, m, a[N];
pair<int, int> g[N];

int main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n >> m;
	F(i, 1, n)
	{
		cin >> a[i];
		(a[i] += a[i - 1]) %= P;
	}

	g[1] = {1, 0};
	g[2] = {0, 1};
	F(i, 3, n)
	{
		g[i].first = (g[i - 2].first - g[i - 1].first + P) % P;
		g[i].second = (g[i - 2].second - g[i - 1].second + P) % P;
	}

	sf1[1] = sf1[2] = 1;
	sf2[1] = 0, sf2[2] = 1;
	F(i, 3, n)
	{
		sf1[i] = (sf1[i - 1] + sf1[i - 2]) % P;
		sf2[i] = (sf2[i - 1] + sf2[i - 2]) % P;
	}
	F(i, 1, n)
	{
		sf1[i] = (sf1[i - 1] + sf1[i]) % P;
		sf2[i] = (sf2[i - 1] + sf2[i]) % P;
	}

	F(i, 1, m)
	{
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1)
		{
			segt.add(1, 1, n, l, r, g[l].first, g[l].second);
		}
		else
		{
			cout << (segt.get_sum(1, 1, n, l, r)
				+ a[r] - a[l - 1] + P) % P << '\n';
		}
	}

	return 0;
}

加强版思路

通过上文对原题的分析，我们可以将区间加斐波那契数列的前若干项，变为加两个斐波那契数列的对应位置项。对于维护平方，也是一个道理：

\[\begin{aligned} \sum_{i=l}^{r}(A_i + kB_i)^2 &= \sum A_i^2 + k^2\sum B_i^2 + k\sum A_iB_i \end{aligned} \]

那么我们只需要预处理 \(B_i^2\) 前缀和，同时维护 \(A_iB_i\) 的区间和即可，又注意到：

\[\begin{aligned} \sum_{i=l}^r(A_i + kB_i)B_i &= \sum A_iB_i + k\sum B_i^2\\ \sum_{i=l}^r(A_i + kB_i)C_i &= \sum A_iC_i + k\sum B_iC_i \end{aligned} \]

而 \(B_iC_i\) 的前缀和也可以预处理，所以加强版问题在这个转化视角下也是容易的。

标签：CF446C,int,题解,sum,sf2,sf1,Fibonacci,tg,那契
From： https://www.cnblogs.com/kyeecccccc/p/17118244.html