P15424 2025 AMBITION

:::epigraph[——《2025 AMBITION》] 抱歉我学不会服从因为我做到 artist beat :::

有一个 Y 形路口，包含四根车道以及它们交出的两个道路单元 $x,y$，以及 $x,y$ 之间的道路连接处。车辆从 $q_1,q_2$ 两车道向前进入路口，通过两个道路单元中的一部分，转向两边的道路。 不妨称 $q_1$ 为左车道，$q_2$ 为右车道。  - $t$ 时刻从左车道进入路口的车辆： - 若左转，则占据 $t$ 时刻的 $x$ 道路单元。 - 若右转，则占据 $t$ 时刻的 $x$ 道路单元，$t+0.5$ 时刻的道路连接处，和 $t+1$ 时刻的 $y$ 道路单元。 - $t$ 时刻从右车道进入路口的车辆： - 若左转，则占据 $t$ 时刻的 $y$ 道路单元，$t+0.5$ 时刻的道路连接处，和 $t+1$ 时刻的 $x$ 道路单元。 - 若右转，则占据 $t$ 时刻的 $y$ 道路单元。 由于道路是单根单行道，所以同一车道中前面的车辆一定比后面的车辆更早进入路口。 你不希望同一时刻有两辆车占据同一道路单元或者占据道路连接处，因为这可能导致交通堵塞。 现在给你两根车道从前往后每辆车的左右转情况，每辆车可以从 $1$ 时刻起的**整数时刻**进入路口。你的任务是安排一种满足条件的每辆车进入路口的时间，并使得最晚离开路口的车辆离开路口的时间最小。

**本题包含多组测试。** 第一行一个正整数 $T$。对于每组测试数据： 第一行两个正整数 $n,m$，分别表示左右车道的车辆数。 第二行一个长度为 $n$ 的字符串，仅包含 `L` 或 `R`。第 $i$ 个字符表示**左车道从靠近路口的一端向后**第 $i$ 辆车是左转（`L`）还是右转（`R`）。 第三行一个长度为 $m$ 的字符串，仅包含 `L` 或 `R`。第 $i$ 个字符表示**右车道从靠近路口的一端向后**第 $i$ 辆车是左转还是右转。

共 $T$ 行，表示每组测试数据的答案。

### 样例 #1 解释 对于第一组数据： - 在第 $1$ 时刻，左车道的第一辆车左转，右车道的第一辆车右转，两辆车互不干涉。 - 在第 $2$ 时刻，左车道的第二辆车右转，这将占用 $2$ 时刻的 $x$ 道路单元，$2.5$ 时刻的道路连接处，和 $3$ 时刻的 $y$ 道路单元。 - 在第 $4$ 时刻，右车道的第二辆车左转，这将占用 $4$ 时刻的 $y$ 道路单元，$4.5$ 时刻的道路连接处，和 $5$ 时刻的 $x$ 道路单元。 - 在第 $5$ 时刻，右车道的第三辆车左转，这将占用 $5$ 时刻的 $y$ 道路单元，$5.5$ 时刻的道路连接处，和 $6$ 时刻的 $x$ 道路单元。 在这种安排下，最晚离开路口的车辆（右车道第三辆车）于 $6$ 时刻离开路口。可以证明，这是最小的最晚离开路口时刻，故输出 $6$。 ### 数据范围 **本题开启捆绑测试。** 对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,m\le 2\times 10^5$，$1\le \sum (n+m)\le 4\times 10^5$，保证输入的表示车流的字符串中只含有 `L` 和 `R`。 | 子任务 | $\sum (n+m)\le$ | 特殊性质 | 得分 | |:-:|:-:|:-:|:-:| | 1 | $20$ | 无 | $15$ | | 2 | $5000$ | 无 | $15$ | | 3 | $8\times 10^4$ | A | $15$ | | 4 | $8\times 10^4$ | B | $10$ | | 5 | $8\times 10^4$ | C | $15$ | | 6 | $2\times 10^5$ | 无 | $10$ | | 7 | $4\times 10^5$ | 无 | $20$ | 特殊性质 A：右车道不存在相邻两辆车右转。 特殊性质 B：对于每组测试数据，右车道至多只有 $10$ 辆右转的车辆满足其下一辆车也是右转的。 特殊性质 C：数据输入文件中 `L` 字符的出现次数不超过 $5000$。 ### 后记 :::epigraph[——《2025 AMBITION》] 拿出成绩证明自己他假装看不明白 :::