题干：给一个阵列 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/cn.aspx?n=bbs/Prob_Solve/M.1553976584.A.1C8.html ※ 编辑: rareone (140.114.216.110), 03/31/2019 04:27:48