[Codeforces 718C] Sasha and Array

Problem Description

Sasha has an array of integers a1, a2, ..., an. You have to perform m queries. There might be queries of two types:

  1. 1 l r x — increase all integers on the segment from l to r by values x;
  2. 2 l r — find , where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7.

In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.

Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?

Solution

构造一个矩阵A=\begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix},那么斐波那契数列的第n项就是A^{n-1}

考虑建立一棵线段树,每个叶子存a[i]所对应的斐波那契数,其他的节点存当前节点所管理区间的区间和,以及lazy-tag

那么第一个操作等价于对区间[l,r]乘上一个A^{x}

第二个操作等于查询区间和

mdzz矩阵快速幂必须在外面弄好,不然进去就要带个log然后就GG

总的时间复杂度为O(m(\log n+\log a_{i}))

 

发表评论