華生，你又犯了一個錯誤
「福爾摩斯，中午吃火腿三明治好嗎？」
「好啊！不過華生，請不要出去太久。」
結果我花了約一個小時才回家，福爾摩斯見到我，咕噥道：「華生，你好像給自己製造了一些麻煩！吃的東西，你是在貝克街的南邊或北邊買的？」
「我到南邊去。那裡的麵包店一條麵包賣一便士，北邊卻要兩便士，貴得要命。同樣一條麵包，居然賣兩倍的價格。」
「可是南邊的肉店價格比較貴，不是嗎？」
「嗯，沒錯，不過火腿只貴四分之一，北邊賣十二便士，南邊賣十五便士。」
「所以我們的午餐總支出是十六便士，但是如果你到北邊買，只要十四便士。這算盤打得可真奇怪，華生，你犯了一個錯誤。」
福爾摩斯繼續說：「老實說，我看到你從南邊的麵包店出來、進肉鋪之前，經過了賣三明治的米莉女士店門口。我看到她的盤子裡還有沒賣完的三明治。每天早上的尖峰時刻過後，她會以每份一便士的價格出清，因為不賣完的話，到頭來只好丟掉。我並不是嫌你的三明治做不好，不過她的三明治的確非常好吃。為什麼你不乾脆用更便宜的價格買更好吃的三明治，也可以省下做三明治的麻煩？」
「但是我已經買了麵包，而且我喜歡親自做三明治。再說，明天以前麵包不吃完會壞掉，那未免太浪費。福爾摩斯，不要忘了非洲還有小孩在挨餓！」
「就算你草草做一份三明治，而不買米莉可口的三明治，也幫不了他們。假使你買了米莉的三明治，把麵包丟掉，然後將省下的幾便士投入捐獻箱，還可以做一些好事。華生，你又犯了一個錯誤。」\((節錄自 \mit{112} 年學測國寫)\)
現在在一條道路上有 \(N\) 間三明治店，\(a_i\) 表示第 \(i\) 間店三明治的售價，為了讓華生不再被福爾摩斯罵，請幫他計算它從第 \(k\) 個位置出發他買三明治的最小代價。
其中，從 \(k\) 走到 \(i\) 買三明治的代價 \(= a_i + |k-i| \)。
輸入格式
第一行輸入兩個正整數 \(N, Q\)，下一行會有 \(N\) 個數字，第 \(i\) 個代表 \(a_i\) 家麵包店所賣的售價。
下一行會有 \(Q\) 個數，表示華生從 \(k\) 出發。
- \(1 \leq N, Q \leq 10^5\)
- \(1 \leq i, k \leq N \)
- \(1 \leq a_i \leq 10^5\)
輸出格式
輸出 \(Q\) 行，對於每一個 \(k\)，請輸出華生可能花費的最小代價。
範例輸入
5 2
2 4 5 3 10
1 5範例輸出
2
4說明
華生在第 \(1\) 個位置時可能的最小代價為在第 \(1\) 間麵包店購買，代價 \(=2+|1-1|=2\)。
華生在第 \(5\) 個位置時可能的最小代價走到第 \(4\) 間麵包店購買，代價 \(=3+|4-5|=4\)。
子題
| #No. | 額外限制 | 分數 |
|---|---|---|
| 1 | 保證 \(N=1\) | 10 |
| 2 | \(1 \leq N,Q \leq 100\) | 20 |
| 3 | 無其他限制 | 70 |
评论
讚喔！不過題解的query 也可以在O(1)得到答案。
睽違已久回來寫這題，其實不用線段樹
前面跟題解一樣分成兩類討論，但由於取兩類的最小值時都是從頭或尾的一個連續段，預處理一下就可以O(1)回答詢問了
所以建議題目N,Q開到1e6