#5756. 「ROI 2026 Day1」体育训练

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2026 Day1 T4. Спортивная тренировка

一些学生正在参加体育课。训练开始时，教室内有 $n$ 个人，随后在训练过程中，又有 $q$ 个人依次加入。这 $n+q$ 名学生的身高各不相同，我们按照身高从矮到高将他们编号为 $1$ 到 $n+q$。

在训练中，学生们要进行传球练习。学生们从左到右排成一排。根据他们排列的顺序，某些学生对会构成合法对。

对于站在位置 $i$ 和 $j$ $(i < j)$ 的两名学生，若满足以下条件之一，则他们构成一个合法对：

• 位置 $i$ 的学生是所有身高矮于位置 $j$ 的学生且站在其左侧的人中，最靠右的那一个；
• 位置 $j$ 的学生是所有身高矮于位置 $i$ 的学生且站在其右侧的人中，最靠左的那一个。

例如，如果学生们按编号顺序排列为 $[6, 7, 3, 5, 1, 2]$，则合法对为：$(6, 2), (6, 7), (7, 2), (3, 2), (3, 5), (5, 2), (1, 2)$。

练习分为两个难度级别，每个级别都有各自的合法传球规则。在任何难度的练习中，都不允许将球传给在同一次练习中已经拿到过球的学生。

在第一级别难度中，一名学生可以将球传给任何与其构成合法对且身高比其矮的学生。 例如，如果排列为 $[6, 7, 3, 5, 1, 2]$，编号为 $3$ 的学生只能传球给编号为 $2$ 的学生；编号为 $5$ 的学生可以传球给编号为 $3$ 和 $2$ 的学生；而编号为 $1$ 的学生不能传球给任何人。

在第二级别难度中，一名学生可以将球传给任何与其构成合法对的学生。 例如，如果排列为 $[6, 7, 3, 5, 1, 2]$，编号为 $3$ 的学生可以传球给编号为 $2$ 和 $5$ 的学生；编号为 $5$ 的学生可以传球给编号为 $3$ 和 $2$ 的学生；而编号为 $1$ 的学生可以传球给编号为 $2$ 的学生。

练习的过程如下：教练选择一个难度级别 $t$。其中一名学生拿到球并进行一次合法传球。接到球的学生再次进行一次合法传球，依此类推。传球过程一直持续到无法进行为止。如果存在多个合法传球目标，可以选择其中任何一个。为了使训练效果最好，学生们会尽可能多地进行传球。

随后，有 $q$ 次新学生加入的情况。每次都会有一名新学生站在当前队伍的最左端或最右端。之后，练习会在相同的难度级别下重新开始。

对于初始的参与者以及每次新加入学生后的队列，你需要确定学生们最多能进行的传球次数。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 2)$，表示练习的难度级别。

第二行包含两个整数 $n$ 和 $q$ $(1 \le n \le 10^5, 0 \le q \le 2 \cdot 10^5)$，分别表示初始的学生人数和后续加入的学生人数。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n + q)$，表示最初从左到右排列的学生编号。保证所有编号各不相同。

接下来的 $q$ 行描述加入的学生。每行包含一个字符（L 或 R）和一个整数 $x$ $(1 \le x \le n + q)$，中间用空格隔开。字符 L 表示编号为 $x$ 的学生站在队伍左侧，R 表示站在右侧。

保证在任何时刻，所有参与练习的学生编号都是唯一的。

输出格式

第一行输出一个整数，表示初始 $n$ 名参与者在难度级别 $t$ 下的最大传球次数。

接下来的 $q$ 行，每行输出一个整数，表示每增加一名参与者后，在相同难度级别下的最大传球次数。

样例 1

输入

1
6 2
6 7 3 5 1 2
L 8
R 4

输出

3
3
5

在第一个样例中，最优策略可以是让编号为 $5$ 的学生开始。第一次传球可以传给编号为 $3$ 的学生，第二次传给编号为 $2$，第三次传给编号为 $1$。在左侧添加编号为 $8$ 的学生不会增加最大传球次数。而在右侧添加编号为 $4$ 的学生后，可以从编号为 $7$ 的学生开始，依次将球传给编号为 $6, 4, 3, 2, 1$ 的学生。

样例 2

输入

2
6 2
6 7 3 5 1 2
L 8
R 4

输出

4
4
6

在第二个样例中，同样可以从编号为 $5$ 的学生开始，获得四次合法传球，依次传给编号为 $3, 2, 7, 6$ 的学生。在左侧添加编号为 $8$ 的学生不会改变最大传球次数，而从右侧添加编号为 $4$ 的学生后，例如从编号为 $7$ 开始，可以依次传球给编号为 $6, 4, 5, 3, 2, 1$。

样例 3

输入

1
5 4
4 3 1 6 2
R 7
L 8
R 9
L 5

输出

3
3
4
5
4

样例 4

输入

2
5 4
9 4 6 8 2
R 1
L 7
R 5
R 3

输出

4
4
5
7
6

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$t$	$n, q$	附加限制	子任务依赖
$1$	$6$	$t = 1$	$n + q \le 16$	无	—
$2$	$4$		$n, q \le 100$		$1$
$3$	$3$		$n \le 1000, q = 0$		—
$4$	$5$		$n, q \le 1000$		$1, 2, 3$
$5$	$3$		$q = 0$		$3$
$6$	$10$		$n = 1$	$a_1 = 1$，学生按编号递增顺序加入	—
$7$	$6$		—	初始参与者、顺序、加入顺序和方向均为随机
$8$	$5$		$n, q \le 50\,000$	无	$1, 2, 3, 4$
$9$	$8$		—		$1 \sim 8$
$10$	$4$	$t = 2$	$n + q \le 16$		—
$11$	$6$		$n, q \le 100$		$10$
$12$	$5$		$n \le 1000, q = 0$		—
$13$	$9$		$n, q \le 1000$		$10, 11, 12$
$14$	$3$		$q = 0$		$12$
$15$	$6$		$n = 1$	$a_1 = 1$，学生按编号递增顺序加入	—
$16$	$6$		—	初始参与者、顺序、加入顺序和方向均为随机
$17$	$7$		$n, q \le 50\,000$	无	$10, 11, 12, 13$
$18$	$4$		—		$10 \sim 17$