题解：P17083 [COTS 2026] 排列 / Permutacije（暂无数据）

· · 题解

分析

如果 (l,r,L,R) 合法。则对 i\in [l,r]，a_i 在 b 中的出现位置 pos_b(i) 满足 pos_b(i) < L\lor pos_b(i)>R。

维护前缀 pos_a(i) 的最小最大值，后缀 pos_a(i) 的最小最大值。设它们分别是 a,b,c,d。

那么 (L,R) 合法，当且仅当 \max(b_{L-1},d_{R+1})-\min(a_{L-1},c_{R+1})=n-(R-L+1)。

从小到大枚举 L-1。双指针维护 i,j 表示：

  1. 对 R+1 \ge \max(i,j)。有 b_{L-1}>d_{R+1},a_{L-1}<c_{R+1}。
  2. 对 \max(i,j) > R+1\ge \min(i,j)。有 b_{L-1}<d_{R+1},a_{L-1}<c_{R+1} 或 b_{L-1}>d_{R+1},a_{L-1}>c_{R+1}。
  3. 对 \min(i,j)>R+1 > L-1。有 b_{L-1}<d_{R+1},a_{L-1}>c_{R+1}。

这三种情况都差不多。以情况 2 中 b_{L-1}<d_{R+1},a_{L-1}<c_{R+1} 举例。

式子化简成 d_{R+1}-(n-R) =c_{L-1} + (L-1)。拿个桶算数量即可。

整体时间复杂度 O(n)。