電神熊寶貝電爽爽

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

百柒級熊寶貝是眾所皆知的臺大資工電神,他喜歡帶著他的Surface到處電人。
而他現在正忙著在氣球盃中電人,但是他卻解不出來pC。
為了舒緩壓力,他離開了座位,先去教別人要怎麼把指考化學考到100分。
接著再到教室外面吃披薩和喝飲料。
打開筆電看了一集JoJo。
又跟脖子等人一起打了幾場風聲。
然後又去吃了一餐品苑。
最後為了減肥,瞬間移動到臺大參加5公里的馬拉松,結果因為晶片沒讀到而完成時間從31'變成了46'47"。而聰明的他推論出:這是一定是替身攻擊!。
雖然熊寶貝在這兩小時內過得很充實,但是他還是要面對現實。請你幫他解決他卡了很久的這題。

Input

問題很簡單:
給一長度為\(n\)的陣列,請且詢問\(q\)次。
對於每次查詢,找到子區間的\(max({a_i-a_j})\)(\(l \leq j \lt i \leq r\), 其中 \(l,r\)為子區間的左、右界線)

第一行包含兩個數字,分別是\(n\)和\(q\)。
第二行有\(n\)個數字,分別代表\(a_1, a_2, a_3 ... a_n\)。 接下來有\(q\)行,分別是\(l, r\),代表查詢子區間的左、右界線(含) 。

Output

總共有\(q\)行,請輸出每次查詢的\(max({a_i-a_j})\)(\(l \leq j \lt i \leq r)\)

Constraints

第 \(1\) 組測資, \(n\leq10^2\), \(q=1\)。 \((35\text{%})\)

第 \(2\) 組測資, \(n\leq10^2\)。 \((25\text{%})\)

第 \(3\) 組測資, \(n\leq10^4\)。 \((15\text{%})\)

第 \(4\) 組測資, \(n\leq2*10^5\)。\((25\text{%})\)

對於所有測資,\(1 \leq q \leq n\), \(0 \leq a_i \leq 10^6\), \(1\leq l < r \leq n\)。

Sample Input
10 4
1 2 6 4 3 7 8 9 0 10
1 6
2 9
3 7
5 6
Sample Output
6
7
5
4

Comments

There are no comments at the moment.