Spinning Round (Hard Version)
Contest: EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: divide and conquer, dp, trees

This is the hard version of the problem. The only difference between the two versions are the allowed characters in $$$s$$$. You can make hacks only if both versions of the problem are solved.

You are given a permutation $$$p$$$ of length $$$n$$$. You are also given a string $$$s$$$ of length $$$n$$$, where each character is either L, R, or ?.

For each $$$i$$$ from $$$1$$$ to $$$n$$$:

- Define $$$l_i$$$ as the largest index $$$j < i$$$ such that $$$p_j > p_i$$$. If there is no such index, $$$l_i := i$$$.
- Define $$$r_i$$$ as the smallest index $$$j > i$$$ such that $$$p_j > p_i$$$. If there is no such index, $$$r_i := i$$$.

Initially, you have an undirected graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and no edges. Then, for each $$$i$$$ from $$$1$$$ to $$$n$$$, add one edge to the graph:

- If $$$s_i =$$$ L, add the edge $$$(i, l_i)$$$ to the graph.
- If $$$s_i =$$$ R, add the edge $$$(i, r_i)$$$ to the graph.
- If $$$s_i =$$$ ?, either add the edge $$$(i, l_i)$$$ or the edge $$$(i, r_i)$$$ to the graph at your choice.

Find the maximum possible diameter over all connected$$$^{\text{∗}}$$$ graphs that you can form. Output $$$-1$$$ if it is not possible to form any connected graphs.

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of $$$p$$$, which are guaranteed to form a permutation.

The third line of each test case contains a string $$$s$$$ of length $$$n$$$. It is guaranteed that it consists only of the characters L, R, and ?.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, output the maximum possible diameter over all connected graphs that you form, or $$$-1$$$ if it is not possible to form any connected graphs.

Constraints:
Time limit: 7.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, there are two connected graphs (the labels are indices):

The graph on the left has a diameter of $$$2$$$, while the graph on the right has a diameter of $$$3$$$, so the answer is $$$3$$$.

In the second test case, there are no connected graphs, so the answer is $$$-1$$$.

Example input:
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
????????????

Example output:
3
-1
-1
4
4
3
5
8

Editorial:
For simplicity, let $$$p_0 = p_{n+1} = +\infty$$$, and let's recalculate the values of $$$l_i$$$ and $$$r_i$$$. Then, the answer is not $$$-1$$$ if for all $$$1 \le i \le n$$$ and $$$p_i < n$$$:
• $$$s_i =~$$$L $$$\implies l_i \ge 1$$$.
• $$$s_i =~$$$R $$$\implies r_i \le n$$$.
• $$$s_i =~$$$? $$$\implies l_i \ge 1$$$ or $$$r_i \le n$$$.
Let $$$dp[tl][tr]$$$ store some set of pairs $$$(a, b)$$$, where for some valid graph:
• $$$a$$$ is a possible depth of a path that starts at index $$$tl$$$ and passes only through indices $$$tl \le i \le tr$$$.
• $$$b$$$ is a possible depth of a path that starts at index $$$tr$$$ and passes only through indices $$$tl \le i \le tr$$$.
• The paths do not intersect.
Let's iterate over all $$$i$$$ in order of increasing $$$p_i$$$. For each $$$i$$$ ($$$tl = l_i$$$ and $$$tr = r_i$$$), we will iterate over all pairs $$$(d_1, d_2)$$$ in $$$dp[tl][i]$$$ and $$$(e_1, e_2)$$$ in $$$dp[i][tr]$$$:
• If $$$s_i \neq $$$ R and $$$tl \ge 1$$$, we can add the edge $$$(tl, i)$$$, so:   Update the answer with $$$\max(ans, d_1 + 1 + \max(d_2, e_1))$$$.  Add the pairs $$$(d_1, e_2)$$$, $$$(d_2 + 1, e_2)$$$, and $$$(e_1 + 1, e_2)$$$ to $$$dp[tl][tr]$$$.
• Update the answer with $$$\max(ans, d_1 + 1 + \max(d_2, e_1))$$$.
• Add the pairs $$$(d_1, e_2)$$$, $$$(d_2 + 1, e_2)$$$, and $$$(e_1 + 1, e_2)$$$ to $$$dp[tl][tr]$$$.
• If $$$s_i \neq $$$ L and $$$tr \le n$$$, we can add the edge $$$(i, tr)$$$, so:   Update the answer with $$$\max(ans, \max(d_2, e_1) + 1 + e_2)$$$.  Add the pairs $$$(d_1, d_2 + 1)$$$, $$$(d_1, e_1 + 1)$$$, and $$$(d_1, e_2)$$$ to $$$dp[tl][tr]$$$.
• Update the answer with $$$\max(ans, \max(d_2, e_1) + 1 + e_2)$$$.
• Add the pairs $$$(d_1, d_2 + 1)$$$, $$$(d_1, e_1 + 1)$$$, and $$$(d_1, e_2)$$$ to $$$dp[tl][tr]$$$.
Turns out, it is enough to store at most three pairs for each $$$dp[tl][tr]$$$. Specifically, it is enough to store:
• One pair with the maximum possible $$$a$$$.
• One pair with the maximum possible $$$b$$$.
• One pair with the maximum possible $$$a + b$$$.
If true, this leads to an $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \log n)$$$ solution, albeit with a large constant factor.
Proof
We will proceed with a proof by induction.
Hypothesis: it is enough to store the three pairs described above.
Base case: for $$$i$$$ with $$$l_i = i - 1$$$ and $$$r_i = i + 1$$$, only the pairs $$$(0, 0)$$$, $$$(1, 0)$$$ and $$$(0, 1)$$$ are possible.
Induction step: For some $$$i$$$, let $$$dp[tl][i]$$$ and $$$dp[i][tr]$$$ only store the three pairs described above.
First of all, we update the answer with the same value:
• When adding the left edge:   If the answer came from $$$d_1 + 1 + d_2$$$, we maximize $$$d_1 + d_2$$$.  If the answer came from $$$d_1 + 1 + e_1$$$, we maximize $$$d_1$$$ and $$$e_1$$$.
• If the answer came from $$$d_1 + 1 + d_2$$$, we maximize $$$d_1 + d_2$$$.
• If the answer came from $$$d_1 + 1 + e_1$$$, we maximize $$$d_1$$$ and $$$e_1$$$.
• When adding the right edge:   If the answer came from $$$d_2 + 1 + e_2$$$, we maximize $$$d_2$$$ and $$$e_2$$$.  If the answer came from $$$e_1 + 1 + e_2$$$, we maximize $$$e_1 + e_2$$$.
• If the answer came from $$$d_2 + 1 + e_2$$$, we maximize $$$d_2$$$ and $$$e_2$$$.
• If the answer came from $$$e_1 + 1 + e_2$$$, we maximize $$$e_1 + e_2$$$.
Secondly, $$$dp[tl][tr]$$$ will store the pairs with the same values of $$$\max a$$$, $$$\max b$$$, and $$$\max (a + b)$$$; as in the case when all pairs are stored on all previous stages:
• When adding the left edge, it is clearly not less optimal to add only the pair $$$(\max(d_1, d_2 + 1, e_1 + 1), e_2)$$$:   When maximizing $$$a$$$, we maximize $$$\max(d_1, d_2 + 1, e_1 + 1)$$$, which we do by maximizing $$$d_1$$$, $$$d_2$$$, or $$$e_1$$$.  When maximizing $$$b$$$, we maximize $$$e_2$$$.  When maximizing $$$a + b$$$, we maximize $$$d_1 + e_2$$$, $$$d_2 + e_2$$$, or $$$e_1 + e_2$$$, which we do by induction.
• When maximizing $$$a$$$, we maximize $$$\max(d_1, d_2 + 1, e_1 + 1)$$$, which we do by maximizing $$$d_1$$$, $$$d_2$$$, or $$$e_1$$$.
• When maximizing $$$b$$$, we maximize $$$e_2$$$.
• When maximizing $$$a + b$$$, we maximize $$$d_1 + e_2$$$, $$$d_2 + e_2$$$, or $$$e_1 + e_2$$$, which we do by induction.
• When adding the right edge, we can only add the pair $$$(d_1, \max(d_2 + 1, e_1 + 1, e_2))$$$:   When maximizing $$$a$$$, we maximize $$$d_1$$$.  When maximizing $$$b$$$, we maximize $$$\max(d_2 + 1, e_1 + 1, e_2)$$$, which we do by maximizing $$$d_2$$$, $$$e_1$$$, or $$$e_2$$$.  When maximizing $$$a + b$$$, we maximize $$$d_1 + d_2$$$, $$$d_1 + e_1$$$, or $$$d_1 + e_2$$$, which we do by induction.
• When maximizing $$$a$$$, we maximize $$$d_1$$$.
• When maximizing $$$b$$$, we maximize $$$\max(d_2 + 1, e_1 + 1, e_2)$$$, which we do by maximizing $$$d_2$$$, $$$e_1$$$, or $$$e_2$$$.
• When maximizing $$$a + b$$$, we maximize $$$d_1 + d_2$$$, $$$d_1 + e_1$$$, or $$$d_1 + e_2$$$, which we do by induction.
Thus, we achieve the same answer by only storing these pairs, which concludes our proof.
Complexity: $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \log n)$$$
Note: there are a number of other possible solutions, please refer to the comments below.