a164. 區間最大連續和 - 高中生程式解題系統

Content

給定一個整數序列A_i, 其中1<=i<=N。

有Q筆詢問，每次詢問一個正整數數對L, R，問閉區間 [A_L, A_R]的最大連續和。

什麼叫最大連續和呢？請參見d784: 連續元素的和

也就是說要找到兩個正整數i, j滿足L <=i <=j <= R，且極大化A_i + A_i+1 + ... + A_j的值。

當i, j有多組解時輸出i最小的、再有多組解輸出j最小的。

Input

輸入含多組測試資料，請用EOF判斷結束。

每組資料：

第一行有兩個正整數N, Q 。

再來一行有以空白分隔的N個整數，依序表示A₁到A_N。

再來會有Q行，每行兩個正整數L, R表示一個詢問。

保證：

單一檔案不超過十筆數據。

1 <= N <= 200,000

1 <= Q <= 100,000

1 <= L <= R <= N

輸入所有數字都是整數且絕對值小於1,000,000,000

Output

每組測資的輸出第一行請輸出"Case x:"表示為第x組測資，從1開始編號。

接下來輸出Q行，每行輸出三個數字依序表示該筆詢問的i, j以及A_i + A_i+1 + ... + A_j的值。

Sample Input #1

10 3
0 0 0 1 0 0 0 -8 -3 5
1 7
8 9
8 10

Sample Output #1

Case 1:
1 4 1
9 9 -3
10 10 5

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (19%): 1.0s , <1M
公開測資點#2 (80%): 3.0s , <10M

Hint ：

第一個檔案就是範例。

第二個檔案共有十組，N=Q=100。

第三個檔案共有兩組，皆為極限測資。

Tags:

DP 區間

出處:

Asia - Nanjing - 2007/2008 [管理者： qychen11@gmail.com

poao899(帥氣傳說勇士) ]