CF1987G2 Spinning Round (Hard Version)

题目描述

这是该问题的困难版本。两种版本的区别仅在于 $s$ 中允许的字符。只有当你同时解决了两个版本的问题时，才能进行 Hack。

给定一个长度为 $n$ 的排列 $p$，以及一个长度为 $n$ 的字符串 $s$，其中每个字符都是 L、R 或 ?。

对于每个 $i$，$1 \le i \le n$：

• 定义 $l_i$ 为最大的 $j < i$，使得 $p_j > p_i$。如果不存在这样的 $j$，则 $l_i := i$。
• 定义 $r_i$ 为最小的 $j > i$，使得 $p_j > p_i$。如果不存在这样的 $j$，则 $r_i := i$。

初始时，你有一个 $n$ 个点（编号为 $1$ 到 $n$）且没有边的无向图。然后，对于每个 $i$，$1 \le i \le n$，向图中添加一条边：

• 如果 $s_i = \text{L}$，则添加边 $(i, l_i)$。
• 如果 $s_i = \text{R}$，则添加边 $(i, r_i)$。
• 如果 $s_i = ?$，你可以选择添加边 $(i, l_i)$ 或 $(i, r_i)$。

请你求出所有可能构造出的连通图中，直径的最大值。如果无法构造出任何连通图，输出 $-1$。

$^*$ 设 $d(s, t)$ 表示从 $s$ 到 $t$ 的任意路径上最少的边数。

图的直径定义为所有点对 $(s, t)$ 中 $d(s, t)$ 的最大值。

输入格式

每组测试数据包含多组测试用例。输入的第一行包含一个整数 $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$ 的元素，保证 $p$ 是一个排列。

第三行包含一个长度为 $n$ 的字符串 $s$，只包含字符 L、R 和 ?。

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

输出格式

对于每组测试用例，输出一个整数，表示所有可能构造出的连通图中直径的最大值。如果无法构造出任何连通图，输出 $-1$。

输入输出样例 #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$。

由 ChatGPT 4.1 翻译