分数: 400 分
问题陈述
高桥已放置 N 直架上的小雕像,具有位置的整数坐标 1 到位置 M.
的初始位置 i第一个雕像(1 \leq i \leq N) 是 A_i。多个小雕像可能位于同一位置。此外,雕像之间不会互相干扰。
这种初始排列称为 状态 0。每个状态都保存有关架子上剩余的雕像组及其各自位置的信息。
我们将创建 Q 新状态,已编号 1, 2, \ldots, Q,按顺序。
状态 j (j = 1, 2, \ldots, Q)是通过以下过程创建的:
- 复制已存在状态的内容 P_j (0 \leq P_j \leq j-1)(架子上剩余的雕像及其位置)用作新状态的初始内容 j.
- 执行以下操作 恰好一次 开启状态 j:
- If C_j is
L:减少状态下架子上每个雕像的位置 j by D_j (将它们滑动 D_j 到左边)。 - If C_j is
R: 增加状态下架子上每个雕像的位置 j by D_j (将它们滑动 D_j 到右侧)。 - 因此,任何位置小于 1 或大于 M 下架并被移除状态 j.
通过复制创建新状态不会以任何方式更改源状态。
注意由于源状态数的方式 选择 P_j ,以状态为根的树结构 形成 0 。
对于每个 j = 1, 2, \ldots, Q,判断状态下已下架的雕像数量 j (即,值 N 减去状态中剩余的雕像数量 j).
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq M (1 \leq i \leq N)
- 0 \leq P_j \leq j - 1 (1 \leq j \leq Q)
- C_j is
LorR(1 \leq j \leq Q) - 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
- 所有输入均为整数(除了 C_j)
输入
N M Q A_1 A_2 \cdots A_N P_1 C_1 D_1 P_2 C_2 D_2 \vdots P_Q C_Q D_Q
- 第一行包含雕像数量 N,货架右端位置 M,以及要创建的状态数 Q,用空格分隔。
- 第二行包含小雕像的初始位置 A_1, A_2, \ldots, A_N,用空格分隔。
- 以下 Q 行描述了如何创建新状态。
- 的 (2 + j)-第行包含源状态号 P_j 状态 j,移动方向 C_j,以及移动量 D_j,用空格分隔。
输出
输出 Q 行。
关于 j第行,输出state中已下架的雕像数量 j (值 N 减去状态中剩余的雕像数量 j)作为整数。
样本输入 1
5 10 4 1 3 5 8 10 0 R 2 0 L 1 1 L 4 2 R 10
示例输出 1
1 1 2 5
示例输入 2
6 7 6 2 2 4 6 7 7 0 L 1 0 R 1 1 R 3 2 L 5 3 L 2 5 R 10
示例输出 2
0 2 3 5 3 6
示例输入 3
15 100 12 1 5 10 20 20 35 50 65 70 80 90 95 100 42 58 0 R 10 0 L 15 1 R 40 1 L 5 2 R 60 2 L 10 3 L 30 4 R 25 5 R 1 6 L 1 8 L 70 10 R 90
示例输出 3
2 3 7 2 10 5 7 4 10 5 10 14
示例输入 4
30 1000000000 25 1 2 3 100 1000 100000 123456789 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 999999999 1000000000 42 4242 424242 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 0 R 1 0 L 1 1 R 999999998 1 L 50 2 R 123456789 2 L 999999999 3 L 500000000 3 R 2 4 R 1000 4 L 1000 5 R 700000000 5 L 200000000 6 R 1 7 L 1 8 R 400000000 9 L 400000000 10 R 600000000 11 L 600000000 12 R 333333333 13 L 333333333 14 R 999999999 15 L 999999999 16 R 123 20 L 456 24 R 789
示例输出 4
1 1 29 5 7 30 29 30 7 7 20 15 30 29 30 18 20 20 17 30 30 30 18 30 30
示例输入 5
1 1 1 1 0 R 1000000000
示例输出 5
1