切換
舊版
前往
大廳
主題

ZeroJudge - d668: 奇怪的老闆 解題心得

Not In My Back Yard | 2020-07-02 00:08:46 | 巴幣 0 | 人氣 600

題目連結:


題目大意:
第一列給定兩正整數 N 、 Q (1 ≦ N ≦ 50000 , 1 ≦ Q ≦ 200000),代表有 N 位員工以及 Q 筆詢問。接著有 N 列輸入,每列給定一正整數,代表編號 1 ~ 編號 N 的員工之薪水。

接著有 Q 列輸入,每列給定兩正整數 a 、 b (0 < a 、 b ≦ N),試問第 a 名員工到第 b 名員工之間所有員工中薪水最大值減去薪水最小值之值為何?



範例輸入:
6 3
1
7
3
4
2
5
1 5
4 6
2 2


範例輸出:
6
3
0


解題思維:
這題類似,建一個可以快速查詢區間最大(最小)值的資料結構。接著將求得的兩種極值互減即是所求的差值。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
你該試一下 zkwTree 有是個有趣的資料結構,泛用度沒 SegmentTree 高,但會快上不少
2020-07-02 14:29:35
Not In My Back Yard
確實可以試一下,感謝建議XD
2020-07-02 15:00:33
追蹤 創作集

作者相關創作

更多創作