[心得] CF1142B Greedy + RMQ + Pointer Jumping
看板Prob_Solve (計算數學 Problem Solving)作者rareone (拍玄)時間5年前 (2019/03/31 04:09)推噓1(1推 0噓 1→)留言2則, 2人參與討論串1/1
題幹：給一個陣列 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
推
06/24 11:32,
06/24 11:32
推
06/24 11:36,
06/24 11:36
推
06/24 11:46,
06/24 11:46
推
06/24 11:48,
06/24 11:48
--
※ 發信站: 批踢踢實業坊(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
推
03/31 11:08,
5年前
, 1F
03/31 11:08, 1F
→
03/31 11:57,
5年前
, 2F
03/31 11:57, 2F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
