Problem : 285 - Hanhan's homework

Problem Statistics

Solved Member: 8　　Submission: 45　　User Tried: 10

Statement:

對於所有的 $n \ge 0$，我們可以定義費波那契數列的第 n 項為
$$f_n = \begin{cases} 1 &\text{,if }n \le 1 \\ f_{n-1} + f_{n-2} &\text{,else} \end{cases}$$

瀚瀚現在不太想寫功課，於是他請你來幫他寫！

功課的內容是這樣的：
現在有一個長度為 n 的數列 $a_1,a_2,...,a_n$，他希望寫一個資料結構來維護以下的三種詢問：

1. 給出 x,v ，將 $a_x$ 的值修改為整數 v

2. 給出 l,r ，求出 $\displaystyle f_{0} \times a_{l} + f_{1} \times a_{l+1} + ... + f_{r-l} \times a_{r}$，也就是求出和：
$$\displaystyle \sum^{r - l}_{x = 0}(f_{x} \times a_{l + x})$$

3.給出 l,r,d，將 $a_l, a_{l+1}, ..., a_{r}$ 的值都加上 d

Input:Output:

輸入第 1 行有 2 個整數 n,m，代表數列的長度以及詢問的次數。
第 2 行有 n 個數字，代表 $a_1,a_2,...,a_n$ 的值。

第 3 行開始的後 m 行，每一行最初有一個數字 c，為 1 到 3 之間的整數之一，代表詢問的種類。
若開頭 c=1，則後面會接 x,v 兩整數。
若開頭 c=2，則後面會接 l,r 兩整數。
若開頭 c=3，則後面會接 l,r,d 三個整數。

限制：
1 ≤ n,m ≤ 200000
0 ≤ a_i ≤ 100000
0 ≤ v,d ≤ 100000
1 ≤ l ≤ r ≤ n

對其中 30% 的測試資料滿足： n ≤ 100，且 m ≤ 10000
對其中 70% 的測試資料滿足：只有第 1 和第 2 種詢問(c 不為 3)

對於每一筆 c=2 的詢問，請輸出一行包含一個數字，代表所求除以 1000000000(10⁹) 的餘數。

Sample Input:Sample Output:

SAMPLE A：
5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5

SAMPLE B：
5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5

SAMPLE A：
12
32
8
50

SAMPLE B：
12
45

Source:

ABBYY Cup 3.0

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	5000ms	262144kb
0-2	5000ms	262144kb
1	5000ms	262144kb	10
2	5000ms	262144kb	10
3	5000ms	262144kb	10
4	5000ms	262144kb	10
5	5000ms	262144kb	10
6	5000ms	262144kb	10
7	5000ms	262144kb	10
8	5000ms	262144kb	10
9	5000ms	262144kb	10
10	5000ms	262144kb	10