Explanation

Firstly, a note on notation: let $F_i$ denote the $i$th Fibonacci number. That is,

In this problem, we will build a segment tree over the array. For a leaf node in the segment tree with value $v$, we will store a pair of values $(F_{v - 1}, F_v)$. For all non-leaf nodes, we will store a pair of values equal to the pair-sum of its children. That is, if a node $u$ has children $v$ and $w$, then $u = (v_0 + w_0, v_1 + w_1)$.

We will use the term cycle by k to denote transforming some pair $(F_{i - 1}, F_i)$ to $(F_{i - 1 + k}, F_{i + k})$. By default, the term cycle refers to cycle by 1.

For each update, we need to cycle each leaf node by some amount $x$ such that the value in a node affected goes from $(F_{v - 1}, F_v)$ to $(F_{v - 1 + x}, F_{v + x})$. We can do this using matrix exponentiation.

First note that for a matrix $\begin{pmatrix} F_{i - 1} & F_i \end{pmatrix}$, we can cycle it by multiplying by $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$. That is,

Inductively, we can cycle by $k$ by multiplying multiple times:

We can use binary exponentiation to quickly compute powers of the two-by-two matrix.

Secondly, we need to utilize the distributive property of matrix multiplication to same-size matrices. That is, if $m_k$ is a one-by-two matrix for $k \in [1, n]$, then the following property is satisfied:

In that way, we can utilize lazy propagation on the segment tree. We will store an integer tag in each node denoting the lazy update, which denotes that we must cycle every node in its subtree by the value of the tag. When propagating, we can simply update the node by binary exponentiating and then multiplying, then storing it in the lazy tag. Querying works as normal on the segment tree.

Implementation

Copy
#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;