題幹：給一個陣列 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 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.216.110 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1553976584.A.1C8.html ※ 編輯: rareone (140.114.216.110), 03/31/2019 04:27:48