題目連結:
題目大意:
第一列給定兩正整數 N 、 Q (1 ≦ N ≦ 50000 , 1 ≦ Q ≦ 200000),代表有 N 位員工以及 Q 筆詢問。接著有 N 列輸入,每列給定一正整數,代表編號 1 ~ 編號 N 的員工之薪水。
接著有 Q 列輸入,每列給定兩正整數 a 、 b (0 < a 、 b ≦ N),試問第 a 名員工到第 b 名員工之間所有員工中薪水最大值減去薪水最小值之值為何?
跟
這題類似,建一個可以快速查詢區間最大(最小)值的資料結構。接著將求得的兩種極值互減即是所求的差值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。