江湖人稱「鐵掌水上飄」的裘千仞，竟然是個招搖撞騙之徒！原來他那水上飄的絕技，不 過是踩在事先暗中設好的木樁之上。若非師父當場出手揭穿這老頭的底細，眾人恐怕還要被他 的虛名所矇騙而渾然不覺。 裘千仞在水中裝設好了 N 個木樁，從左到右排成一排，第 i 個木樁的高度為 Hi，保證是 1 到 N 的排列。但由於家傳武藝的罩門，他並不能隨便亂施展輕功，對於每次跳躍而言，必 須保證兩點之間所有的木樁高度，比此次跳躍的起終點都低。舉例來說，若高度依序為 3, 1, 2， 那他可以從第一個跳到第三個木樁；但在 3, 2, 1 的情況就不行，因為第二個木樁比第三個木樁 還要高。值得注意的是，每個木樁都一定可以跳到相鄰的木樁，因為中間沒有任何其他木樁。 黃藥師安排了 Q 次試驗，第 i 次要讓裘千仞從第 Li 個木樁移動到第 Ri 個木樁。他可以 跳躍很多次，但限制只能往右跳，而且裘千仞會選擇跳躍次數最少的路徑。為了破解裘千仞的 輕功，黃藥師想知道他第 Ki 次跳躍後在哪個木樁上，再給他致命一擊。於是要麻煩聰明的你， 為每次試驗提供這個預測，或是回報他根本早就抵達終點、來不及了。
輸入的第一行是兩個正整數 N, Q，代表木樁總數量和試驗次數。第二行有 N 個正整數， 代表每個木樁的高度 Hi。接下來有 Q 行，第 i 行有三個正整數 Li , Ri , Ki，代表黃藥師在第 i 次試驗中，好奇裘千仞從第 Li 個木樁移動到第 Ri 個木樁，第 Ki 次跳躍後會在哪裡。
• 2 ≤ N ≤ 2 · 105
• 1 ≤ Q ≤ 2 · 105
• 1 ≤ Li < Ri ≤ N
• 1 ≤ Ki ≤ N
• 保證 Hi 是一個 1 到 N 的排列。
輸出 Q 個整數，第 i 個數字代表第 i 次試驗的答案。若此次試驗的跳躍數量小於 Ki，輸 出 −1。否則輸出第 Ki 次跳躍後的位置。
3 1 2 3 1 1 3 1
2
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||