← 返回题目列表

AtCoder · awc0085_d

D. 组织分支货架

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥已放置 N 直架上的小雕像,具有位置的整数坐标 1 到位置 M.

的初始位置 i第一个雕像(1 \leq i \leq N) 是 A_i。多个小雕像可能位于同一位置。此外,雕像之间不会互相干扰。

这种初始排列称为 状态 0。每个状态都保存有关架子上剩余的雕像组及其各自位置的信息。

我们将创建 Q 新状态,已编号 1, 2, \ldots, Q,按顺序。

状态 j (j = 1, 2, \ldots, Q)是通过以下过程创建的:

  1. 复制已存在状态的内容 P_j (0 \leq P_j \leq j-1)(架子上剩余的雕像及其位置)用作新状态的初始内容 j.
  2. 执行以下操作 恰好一次 开启状态 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 L or R (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