← 返回题目列表

Codeforces · 1987/G2

G2. 旋转圆(困难版)

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

这是问题的困难版本。两个版本之间的唯一区别是 $$$s$$$ 中允许的字符。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给你一个长度为 $$$n$$$ 的排列 $$$p$$$。您还会获得一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中每个字符是 L、R 或 ?。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$:

- 将 $$$l_i$$$ 定义为最大索引 $$$j < i$$$,使得 $$$p_j > p_i$$$。如果没有这样的索引,$$$l_i := i$$$。
- 将 $$$r_i$$$ 定义为最小索引 $$$j > i$$$,使得 $$$p_j > p_i$$$。如果没有这样的索引,$$$r_i := i$$$。

最初,您有一个无向图,其中有 $$$n$$$ 个顶点(编号从 $$$1$$$ 到 $$$n$$$)且没有边。然后,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,向图中添加一条边:

- 如果 $$$s_i =$$$ L,则将边 $$$(i, l_i)$$$ 添加到图形中。
- 如果 $$$s_i =$$$ R,则将边 $$$(i, r_i)$$$ 添加到图形中。
- 如果 $$$s_i =$$$ ?,则根据您的选择将边 $$$(i, l_i)$$$ 或边 $$$(i, r_i)$$$ 添加到图表中。

找出您可以形成的所有连接$$$^{\text{*}}$$$ 图中的最大可能直径。如果无法形成任何连通图,则输出 $$$-1$$$。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — 排列 $$$p$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p$$$ 的元素,保证形成排列。

每个测试用例的第三行包含一个长度为$$$n$$$的字符串$$$s$$$。确保它仅由字符 L、R 和 ? 组成。

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

输出

对于每个测试用例,输出您形成的所有连通图的最大可能直径,如果无法形成任何连通图,则输出 $$$-1$$$。

示例

输入 #1

8
5
2 1 4 3 5
R?RL?
2
1 2
LR
3
3 1 2
L?R
7
5 3 1 6 4 2 7
?R?R?R?
5
5 2 1 3 4
?????
6
6 2 3 4 5 1
?LLRLL
8
1 7 5 6 2 8 4 3
?R??????
12
6 10 7 1 8 5 12 2 11 3 4 9
????????????

输出 #1

3
-1
-1
4
4
3
5
8

注意

在第一个测试用例中,有两个连通图(标签是索引):

左边的图形的直径为$$$2$$$,右边的图形的直径为$$$3$$$,所以答案是$$$3$$$。

在第二个测试用例中,没有连通图,因此答案是 $$$-1$$$。