Sasha and Array

Explicación

En primer lugar, una nota sobre la notación: sea $F_i$ el $i$ -ésimo número de Fibonacci. Es decir,

F_i = \begin{cases} 0 & i = 0 \\ 1 & i = 1 \\ F_{i - 1} + F_{i - 2} & i \geq 2 \\ \end{cases}

En este problema, construiremos un árbol de segmentos sobre el arreglo. Para un nodo hoja del árbol de segmentos con valor $v$ , guardaremos un par de valores $(F_{v - 1}, F_v)$ . Para todos los nodos que no son hojas, guardaremos un par de valores igual a la suma por pares de sus hijos. Es decir, si un nodo $u$ tiene hijos $v$ y $w$ , entonces $u = (v_0 + w_0, v_1 + w_1)$ .

Usaremos el término ciclar en k para denotar transformar algún par $(F_{i - 1}, F_i)$ en $(F_{i - 1 + k}, F_{i + k})$ . Por defecto, el término ciclar se refiere a ciclar en 1.

Para cada actualización, necesitamos ciclar cada nodo hoja en alguna cantidad $x$ de modo que el valor en un nodo afectado pase de $(F_{v - 1}, F_v)$ a $(F_{v - 1 + x}, F_{v + x})$ . Podemos hacer esto usando exponenciación de matrices.

Nótese primero que para una matriz $\begin{pmatrix} F_{i - 1} & F_i \end{pmatrix}$ , podemos ciclarla multiplicando por $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$ . Es decir,

\begin{pmatrix} F_i & F_{i + 1} \end{pmatrix} = \begin{pmatrix} F_{i - 1} & F_i \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

Inductivamente, podemos ciclar en $k$ multiplicando varias veces:

\begin{pmatrix} F_{i - 1 + k} & F_{i + k} \end{pmatrix} = \begin{pmatrix} F_{i - 1} & F_i \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^k

Podemos usar exponenciación binaria para calcular rápidamente potencias de la matriz dos por dos.

En segundo lugar, necesitamos utilizar la propiedad distributiva de la multiplicación de matrices para matrices del mismo tamaño. Es decir, si $m_k$ es una matriz uno por dos para $k \in [1, n]$ , entonces se satisface la siguiente propiedad:

(m_1 + m_2 + \dots + m_n) \cdot \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = m_1 \cdot \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} + m_2 \cdot \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} + \dots + m_n \cdot \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

De esa forma, podemos usar propagación perezosa en el árbol de segmentos. Guardaremos una etiqueta entera en cada nodo que denota la actualización perezosa, la cual indica que debemos ciclar cada nodo de su subárbol en el valor de la etiqueta. Al propagar, podemos simplemente actualizar el nodo con exponenciación binaria y luego multiplicar, y guardarlo en la etiqueta perezosa. Consultar funciona de forma normal en el árbol de segmentos.

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
#define f first
#define s second
 
using ll = long long;
using pll = pair<ll, ll>;
 
const int MAXN = 1e5 + 1;
const ll MOD = 1e9 + 7;
 
// BeginCodeSnip{Matrix Operations}
using Matrix = array<array<ll, 2>, 2>;
 
// multiplies two two-by-two matrices
Matrix multiply(const Matrix &a, const Matrix &b) {
	return {(a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD,
	        (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD,
	        (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD,
	        (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD};
}
 
// multiplies a one-by-two matrix with a two-by-two matrix
pll multiply(const pll &a, const Matrix &b) {
	return {(a.f * b[0][0] + a.s * b[1][0]) % MOD,
	        (a.f * b[0][1] + a.s * b[1][1]) % MOD};
}
 
// returns {0, 1, 1, 1,} to the power of n
Matrix pow(ll n) {
	Matrix res = {1, 0, 0, 1};   // identity matrix
	Matrix base = {0, 1, 1, 1};  // fibonacci matrix
	for (; n; n >>= 1) {         // binary exponentiation (log n)
		if (n & 1) { res = multiply(res, base); }
		base = multiply(base, base);
	}
	return res;
}
// EndCodeSnip
 
int N, Q;
pll tree[MAXN * 4];
ll lazy[MAXN * 4];
 
// returns the pair-sum of a and b
pll merge(const pll &a, const pll &b) { return {(a.f + b.f) % MOD, (a.s + b.s) % MOD}; }
 
// pushes lazy update in t to its children
void pushdown(int t) {
	if (lazy[t] == 0) return;
	tree[t << 1] = multiply(tree[t << 1], pow(lazy[t]));
	lazy[t << 1] += lazy[t];
	tree[t << 1 | 1] = multiply(tree[t << 1 | 1], pow(lazy[t]));
	lazy[t << 1 | 1] += lazy[t];
	lazy[t] = 0;
}
 
// cycle range from l to r by v
void update(int l, int r, ll v, int t = 1, int tl = 1, int tr = N) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		tree[t] = multiply(tree[t], pow(v));
		lazy[t] += v;
		return;
	}
	pushdown(t);
 
	int tm = (tl + tr) >> 1;
	update(l, r, v, t << 1, tl, tm);
	update(l, r, v, t << 1 | 1, tm + 1, tr);
	tree[t] = merge(tree[t << 1], tree[t << 1 | 1]);
}
 
// query sum from l to r
ll query(int l, int r, int t = 1, int tl = 1, int tr = N) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return tree[t].f; }
	pushdown(t);
 
	int tm = (tl + tr) >> 1;
	return (query(l, r, t << 1, tl, tm) + query(l, r, t << 1 | 1, tm + 1, tr)) % MOD;
}
 
int main() {
	cin >> N >> Q;
	fill_n(tree, MAXN * 4, pll{0, 1});
	for (int i = 1; i <= N; i++) {
		ll a;
		cin >> a;
		update(i, i, a);
	}
 
	while (Q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r;
			ll v;
			cin >> l >> r >> v;
			update(l, r, v);
		} else if (t == 2) {
			int l, r;
			cin >> l >> r;
			cout << query(l, r) << '\n';
		}
	}
}