← 返回题目列表

Codeforces · 2030/D

D. QED 最喜欢的排列

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

QED 被赋予长度 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$。他还有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 $$$\texttt{L}$$$ 和 $$$\texttt{R}$$$。 QED 只喜欢按非降序排序的排列。要对 $$$p$$$ 进行排序,他可以选择以下任意操作并执行任意次数:

- 选择一个索引 $$$i$$$ 使得 $$$s_i = \texttt{L}$$$。然后,交换 $$$p_i$$$ 和 $$$p_{i-1}$$$。保证$$$s_1 \neq \texttt{L}$$$。
- 选择一个索引 $$$i$$$ 使得 $$$s_i = \texttt{R}$$$。然后,交换 $$$p_i$$$ 和 $$$p_{i+1}$$$。保证$$$s_n \neq \texttt{R}$$$。

他还收到了 $$$q$$$ 查询。在每个查询中,他选择一个索引 $$$i$$$ 并将 $$$s_i$$$ 从 $$$\texttt{L}$$$ 更改为 $$$\texttt{R}$$$ (或从 $$$\texttt{R}$$$ 更改为 $$$\texttt{L}$$$)。请注意,更改是持久的。

每次查询后,他都会询问您是否可以通过执行上述操作任意多次来按非降序对 $$$p$$$ 进行排序。请注意,在回答每个查询之前,排列 $$$p$$$ 会重置为其原始形式。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) – 排列的长度和查询的数量。

以下行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$,$$$p$$$ 是排列)。

以下行包含 $$$n$$$ 字符 $$$s_1s_2 \ldots s_n$$$。保证 $$$s_i$$$ 是 $$$\texttt{L}$$$ 或 $$$\texttt{R}$$$,$$$s_1 = \texttt{R}$$$,并且 $$$s_n = \texttt{L}$$$。

以下 $$$q$$$ 行包含一个整数 $$$i$$$ ($$$2 \leq i \leq n-1$$$),表示 $$$s_i$$$ 从 $$$\texttt{L}$$$ 更改为 $$$\texttt{R}$$$ (或从 $$$\texttt{R}$$$ 更改为$$$\texttt{L}$$$)。

保证所有测试用例的 $$$n$$$ 和 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,如果可能,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yES”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

3
5 3
1 4 2 5 3
RLRLL
2
4
3
8 5
1 5 2 4 8 3 6 7
RRLLRRRL
4
3
5
3
4
6 2
1 2 3 4 5 6
RLRLRL
4
5

输出 #1

YES
YES
NO
NO
YES
NO
NO
NO
YES
YES

注意

在第一个测试用例中,第一个查询之后的 $$$s = \texttt{RRRLL}$$$ 。 QED 可以使用以下操作对 $$$p$$$ 进行排序:

- 最初,$$$p = [1,4,2,5,3]$$$。
- 选择 $$$i = 2$$$ 并将 $$$p_2$$$ 与 $$$p_{3}$$$ 交换。现在,$$$p = [1,2,4,5,3]$$$。
- 选择 $$$i = 5$$$ 并将 $$$p_5$$$ 与 $$$p_{4}$$$ 交换。现在,$$$p = [1,2,4,3,5]$$$。
- 选择 $$$i = 4$$$ 并将 $$$p_4$$$ 与 $$$p_{3}$$$ 交换。现在,$$$p = [1,2,3,4,5]$$$,按非降序排列。

可以证明,在第一个测试用例的所有三个更新之后不可能对数组进行排序。