a224. pK I'm Feeling Lucky - 旦旦解題農場

內容

有$n$個炸雞

每一隻炸雞都有不同的好吃量值$a_i$

設$b$為$a$照量值排序後的數列

其中$b_j$的值對應到$a_i$

$l,r$是要求的範圍

好吃度$c_i$的公式如下

因為一次只能拿兩隻，所以要選最好的兩隻

現在請你寫一個程式求要拿哪兩隻

輸入說明

單測資點單筆測資

測資第一行會有一個數$n$代表有$n$隻炸雞

第二行會有$n$個數$a_i$

第三行以後會有$m$筆詢問

每筆詢問會有兩個數字$l,r$

$a_i$保證不重複

$-2^{31} \leq a_i < 2^{31}$

$0 < l \leq r \leq n \leq 10^6$

$0 < m \leq 10^5$

輸出說明

對於每筆詢問輸出一行，該行包含一個數字

輸出在$[l,r]$區間中好吃度$c_i$最高的兩個$a_i$值總和

範例輸入

10
1 5 4 2 3 6 7 9 8 0
1 10
2 4

範例輸出

9
7

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 10.0s , <10M
公開測資點#4 (20%): 1.0s , <50M

提示：

標籤:

segment tree

出處:

108年學年度復旦程式設計班初階班期中考 [管理者：

fdhs107_KonChin... (konchin)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」