[心得] CF1142B Greedy + RMQ + Pointer Jumping

[rareone (拍玄)]

題幹：給一個陣列 A 跟一個排列 P ，接著很多詢問下來

每一個詢問問 A[l, r] 有沒有 subsequence s.t. 他是 P 的 cyclic shift

(For more explaination for the term 'cyclic shift',
please read the note in orginal problem)

作法：
May assume 排列是 [1 ,.., n] ，這樣我們只要看 A[i] - 1 mod n 就好

首先，對於每個 A[i] 我們都有辦法預處理好
「若他當右界，則最右的邊界 last[i] 使得 A[last[i] .. i] 包含一個 cyclic shift
且該 cyclic shift 的最後一個數字是 A[i]」的陣列 last

很顯然地，如果 n = 2 ，我們只要記得前個數字就好，非常方便
但如果是 n = 3 呢？
先算好前一個數字 last[i] 然後再 iterate last[i] = last[last[i]]
如果 n 很大，我們要一次挑 n - 1 步，只要快速冪
(1-outdegree graph 的話叫 pointer jumping)
就可以跳到 n - 1 步之後的結果了

接著對於每一個詢問 l, r ，我們只要看 max(last[l, r]) 是不是小於 l 就好，有的話代表
從某個位置開始往前到 l 之前就出現一個 cyclic shift ，而這可以用靜態 RMQ 解決

我的程式碼：https://codeforces.com/contest/1142/submission/52047490

--
 標題  [ＸＤ] 當有人開始哼冰與火之歌的主題曲                                  
中文翻譯:https://www.youtube.com/watch?v=cYiUj7_ulvM
推 halfsummer: 龍大要多學學，人家翻得恰到好處
推 ro134360: XDD
推 snickle: 謝謝大大精闢的翻譯( 插霉 )ﾉ
推 HornyDragon: ............
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.216.110
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1553976584.A.1C8.html
※ 編輯: rareone (140.114.216.110), 03/31/2019 04:27:48
推 HanaYukii: 推推 昨天想好久沒想出來
→ rareone: 後來看到 DFS 好像就可以了，只是我還是覺得 jump 好寫