POJ 2452 Sticks：RMQ + 二分查找最大合法區間

問題描述

給定長度互不相同的 n 根棍子排成一排。找 i S_i 且 < S_j，最大化 j-i。無解輸出 -1。

解題思路：RMQ 預處理 + 雙重二分

1. RMQ 構建：O(n log n) 預處理區間最值，O(1) 查詢任意區間最大值/最小值。
2. 固定左端點 i：
   • 第一次二分：找最遠 r 使得 min(i..r) == a[i]（即 a[i] 為區間最小值）。
   • 第二次二分：在 [i, r] 內找最大值位置，作為右端點 j。
3. 遍歷所有 i，取最大 j-i。

關鍵代碼片段