a164: 區間最大連續和
Tags : DP 區間
Accepted rate : 94人/163人 ( 58% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-06-16 16:11

Content

 

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

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

 

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

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

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

 

 

 

Input

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

 

每組資料:

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

再來一行有以空白分隔的N個整數,依序表示A1到AN

再來會有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以及Ai + Ai+1 + ... + Aj的值。

 

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 [管理者:
poao899 (帥氣傳說勇士)
]


ID User Problem Subject Hit Post Date
26430
ck1090758@gl... (peienwu)
a164
測資怪怪的
71 2021-08-06 18:39
24401
711004@stu.c... (牟宗晞)
a164
提示
291 2021-02-14 11:10
24400
711004@stu.c... (牟宗晞)
a164
加強測資
276 2021-02-14 11:09