数轴移动忽略指定区间的唯一访问点计数高效算法问询

核心思路 #

忽略区间[u,v]后，路径分为**前缀（1_{u-1）**和**后缀（v+1}N）**两部分：先执行前缀指令到达位置P，再从P出发执行后缀指令。由于每次移动都是相邻整数，路径访问的唯一点等价于路径覆盖的最小到最大整数区间内的所有数，数量为max - min + 1。最终结果等于前缀区间的点数 + 后缀区间的点数 - 两个区间的重叠点数（避免重复计数）。

预处理数组 #

提前计算以下数组（所有数组均为1-based索引，pre_pos[0] = 0，suf_dis[N+1] = 0，suf_min_offset[N+1] = suf_max_offset[N+1] = 0）：

1. 前缀位置与区间边界

   • pre_pos[i]：执行前i个指令后的位置，pre_pos[i] = pre_pos[i-1] + 1（若第i个字符为'R'），否则pre_pos[i] - 1。
   • pre_min[i]：前i个指令路径中的最小位置，pre_min[i] = min(pre_min[i-1], pre_pos[i])。
   • pre_max[i]：前i个指令路径中的最大位置，pre_max[i] = max(pre_max[i-1], pre_pos[i])。

2. 后缀位移与相对偏移边界

   • suf_dis[i]：执行第i到N个指令的总位移，suf_dis[i] = suf_dis[i+1] + 1（若第i个字符为'R'），否则suf_dis[i+1] - 1。
   • suf_min_offset[i]：从第i个指令开始，相对于起点的最小位移偏移量，suf_min_offset[i] = min(dx, dx + suf_min_offset[i+1])（dx为第i个字符对应的位移：'R'是+1，'L'是-1）。
   • suf_max_offset[i]：从第i个指令开始，相对于起点的最大位移偏移量，suf_max_offset[i] = max(dx, dx + suf_max_offset[i+1])。

查询处理步骤 #

对每个查询[u, v]：

1. 计算前缀部分

   • 若u=1，前缀为空，len1 = 1（仅原点0），min1 = max1 = 0，P = 0。
   • 否则，min1 = pre_min[u-1]，max1 = pre_max[u-1]，len1 = max1 - min1 + 1，P = pre_pos[u-1]。

2. 计算后缀部分

   • 若v=N，后缀为空，len2 = 0。
   • 否则，min_offset = suf_min_offset[v+1]，max_offset = suf_max_offset[v+1]，min2 = P + min_offset，max2 = P + max_offset，len2 = max2 - min2 + 1。

3. 计算重叠区间长度

   • 重叠左边界：overlap_left = max(min1, min2)
   • 重叠右边界：overlap_right = min(max1, max2)
   • 重叠长度：overlap = max(0, overlap_right - overlap_left + 1) if overlap_right >= overlap_left else 0

4. 最终结果

   • result = len1 + len2 - overlap

复杂度分析 #

• 预处理：O(N)，仅需两次线性遍历（正向处理前缀，反向处理后缀）。
• 查询：O(1)，每个查询仅需常数次计算，完全支持1e5级别的即时查询。

内容的提问来源于stack exchange，提问作者joshua