2016年2月25日 星期四

[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
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={1,if n≤1fn−1+fn−2,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 ≤ ai ≤ 100000
0 ≤ v,d ≤ 100000
1 ≤ l ≤ r ≤ n

對其中 30% 的測試資料滿足: n ≤ 100,且 m ≤ 10000
對其中 70% 的測試資料滿足:只有第 1 和第 2 種詢問(c 不為 3)
Output:
對於每一筆 c=2 的詢問,請輸出一行包含一個數字,代表所求除以 1000000000(109) 的餘數。
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:
TestTimeMemoryScore
0-15000ms262144kb
0-25000ms262144kb
15000ms262144kb10
25000ms262144kb10
35000ms262144kb10
45000ms262144kb10
55000ms262144kb10
65000ms262144kb10
75000ms262144kb10
85000ms262144kb10
95000ms262144kb10
105000ms262144kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原