[HOJ 285][ABBYY Cup 3.0]Hanhan's homework (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/285_files/extensions/MathMenu.js

HSNU Online Judge

• Index
• User
• Problem
  • Vol.0
  • Vol.1
  • Vol.2
  • Vol.3
  • Vol.4
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 285 - Hanhan's homework

Problem Statistics

Solved Member: 8　　Submission: 45　　User Tried: 10

Problem：

對於所有的 n≥0， 我們可以定義費波那契數列的第 n 項為
fn={1fn−1+fn−2,if n≤1,else

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

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

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

2. 給出 l,r ，求出 f0×al+f1×al+1+...+fr−l×ar，也就是求出和：
∑x=0r−l(fx×al+x)

3.給出 l,r,d，將 al,al+1,...,ar 的值都加上 d

Input：

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

第 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)

Output：

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

Sample Input：

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 Output：

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

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。