题目详细题解

题意简述

给定长度为 $n$ 的数组 $a$ 和模数 $m$，以及一个长度为 $n$ 的指令字符串 $s$（只包含 'L' 和 'R'）。
按顺序执行指令，每步先输出当前数组所有元素乘积 $\mod m$，然后：

• 若指令为 'L'，删除数组最左元素；
• 若指令为 'R'，删除数组最右元素。

要求输出每一步的余数。

问题难点

直接模拟的时间复杂度为 $O(n^2)$，因为每次都需要重新计算乘积（$n$ 步 × 每步最多 $n$ 个元素相乘）。
$n$ 总和可达 $2\times 10^5$，因此需要 $O(n)$ 或 $O(n \log n)$ 算法。

核心思路

关键观察：

如果按题目顺序（正向）操作，删除元素后乘积会变小，难以直接递推。
但如果反过来思考：从最后一次操作之后（数组为空）开始，逆序执行指令，那么“删除”就变成了“添加”元素，乘积只会乘上新元素，容易维护。

具体来说：

1. 正向：第 $i$ 步输出 $P_i = \prod_{k \in \text{当前数组}} a_k \pmod{m}$，然后删一个元素。
2. 逆向：从最后一步（数组只剩 1 个元素）开始，逆序遍历指令，每步“添加”被删除的元素，新乘积 = 旧乘积 × 新元素 $\pmod{m}$。

最终把逆向求出的结果再逆序输出，就是正向答案。

算法步骤

1. 确定最后剩下的元素
   正向模拟删除过程（不计算乘积，只移动左右指针），找出最后剩下的元素下标。
   设初始 $l = 0$，$r = n-1$。遍历前 $n-1$ 条指令：

   • 若 $s[i] = \text{'L'}$，则 $l$ 加 $1$；
   • 若 $s[i] = \text{'R'}$，则 $r$ 减 $1$。
     结束后 $l = r$，即最后剩下的元素下标。

2. 逆向构造答案数组 $b$
   设 $b[n-1] = a[l] \mod m$（最后一步的余数）。
   然后从 $i = n-2$ 递减到 $0$：

   • 若 $s[i] = \text{'L'}$，说明正向时第 $i$ 步删了最左元素，那么逆向时我们应添加这个最左元素到当前段左边。
     注意：因为正向删除时 $l$ 递增，逆向添加时 $l$ 应递减。
     所以 --l，然后 $b[i] = (b[i+1] \times a[l]) \mod m$。
   • 若 $s[i] = \text{'R'}$，说明正向时第 $i$ 步删了最右元素，逆向添加时应 ++r，然后 $b[i] = (b[i+1] \times a[r]) \mod m$。

3. 输出
   $b[0], b[1], \dots, b[n-1]$ 即为所求。

正确性验证

• 正向：第 $i$ 步输出时数组为 $[a[l_i], a[l_i+1], \dots, a[r_i]]$，乘积为 $P_i$。
• 逆向：$b[i]$ 表示正向第 $i$ 步后数组的乘积（即正向第 $i+1$ 步输出）。
  因为逆向过程正好是添加回正向删除的元素，且乘法模 $m$ 可交换，所以 $b[i]$ 正确。

时间复杂度

• 找最后剩余元素：$O(n)$
• 逆向构造 $b$：$O(n)$
• 总复杂度 $O(n)$，满足要求。

代码注解（对照标程）

int l = 0, r = n - 1;
// 正向模拟删除，找出最后剩下的元素下标
for (int i = 0; i < n - 1; i++) {
    if (s[i] == 'L') l++;
    else r--;
}
// 此时 l == r

vector<int> b(n);
// 最后一步的余数
b[n - 1] = a[l] % m;

// 逆向构造
for (int i = n - 2; i >= 0; i--) {
    if (s[i] == 'L') {
        // 正向删最左，逆向加回最左
        b[i] = (b[i + 1] * a[--l]) % m;
    } else {
        // 正向删最右，逆向加回最右
        b[i] = (b[i + 1] * a[++r]) % m;
    }
}

// 输出 b[0] 到 b[n-1]
for (int i = 0; i < n; i++) {
    cout << b[i] << " ";
}

示例验证（以第一组数据为例）

输入：

4 6
3 1 4 2
LRRL

• 正向删除过程：

  • 初始 $[3,1,4,2]$，输出 $24\mod6=0$，删左 → $[1,4,2]$
  • 输出 $8\mod6=2$，删右 → $[1,4]$
  • 输出 $4\mod6=4$，删右 → $[1]$
  • 输出 $1\mod6=1$，删左 → $[]$

• 逆向构造：

  • 最后剩 $a[1]=1$，$b[3]=1$
  • $i=2$，$s[2]=R$，$r$ 从 $1$ 变 $2$，$b[2]=1\times a[2]=1\times4=4$
  • $i=1$，$s[1]=R$，$r$ 从 $2$ 变 $3$，$b[1]=4\times a[3]=4\times2=8\mod6=2$
  • $i=0$，$s[0]=L$，$l$ 从 $1$ 变 $0$，$b[0]=2\times a[0]=2\times3=6\mod6=0$

得到 $b = [0,2,4,1]$，与输出一致。

总结

核心技巧：
正向删除难以维护乘积 → 逆向添加，将删除操作转化为乘法操作，利用模运算保持数值范围，实现 $O(n)$ 解法。