← 返回题目列表

Codeforces · 1607/D

D. 蓝红排列

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

给定一个整数数组 $$$a$$$,长度为 $$$n$$$。数组的元素可以不同也可以相同。

数组的每个元素的颜色为蓝色或红色。数组中没有未绘制的元素。下面描述的两个操作之一可以通过一个步骤应用于数组:

- 您可以选择任何蓝色元素并将其值减少$$$1$$$;
- 或者您可以选择任何红色元素并将其值增加 $$$1$$$。

根本没有某种颜色的元素的情况也是可能的。例如,如果整个数组颜色为蓝色或红色,则其中一项操作将变得不可用。

确定是否可以执行 $$$0$$$ 或更多步骤,使得结果数组是从 $$$1$$$ 到 $$$n$$$ 的数字排列?

换句话说,检查是否存在一系列步骤(可能为空),使得在应用它之后,数组 $$$a$$$ 按某种顺序包含从 $$$1$$$ 到 $$$n$$$ (含)的所有数字,每个数字恰好一次。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试中输入数据集的数量。

每组输入数据的描述由三行组成。第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 原始数组 $$$a$$$ 的长度。第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) - 数组元素本身。

第三行的长度为 $$$n$$$,仅由字母“B”和/或“R”组成:如果 $$$a_i$$$ 为蓝色,则第 $$$i$$$ 个字符为“B”;如果为红色,则为“R”。

保证所有输入集的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$t$$$ 行,每行包含输入的相应测试用例的答案。如果相应的数组可以转换为排列,则打印 YES 作为答案,否则打印 NO。

您可以在任何情况下打印答案(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定答案)。

示例

输入 #1

8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR

输出 #1

YES
NO
YES
YES
NO
YES
YES
YES

注意

在示例的第一个测试用例中,可以执行以下移动序列:

- 选择$$$i=3$$$,元素$$$a_3=5$$$是蓝色的,所以我们减少它,我们得到$$$a=[1,2,4,2]$$$;
- 选择$$$i=2$$$,元素$$$a_2=2$$$是红色的,所以我们增加它,我们得到$$$a=[1,3,4,2]$$$;
- 选择$$$i=3$$$,元素$$$a_3=4$$$是蓝色的,所以我们减少它,我们得到$$$a=[1,3,3,2]$$$;
- 选择$$$i=2$$$,元素$$$a_2=2$$$是红色的,所以我们增加它,我们得到$$$a=[1,4,3,2]$$$。

我们知道 $$$a$$$ 是一个排列。因此答案是肯定的。