P9019 [USACO23JAN] Tractor Paths P

**注意：这个问题的时间限制是4秒，内存限制是512MB，是默认值的两倍。** 农民约翰有 $N (2 \le N \le 2 \cdot 10^5)$ 台拖拉机, 其中第 $i$ 台拖拉机只能在序列 $[l_i,r_i]$ 内使用。拖拉机有左端点 $l_1

第一行输入两个整数 $N$ 和 $Q$，表示有 $N$ 台拖拉机和 $Q$ 次询问。 第二行输入一个长度为 $2N$ 的字符串，由大写字母 `L` 和 `R` 组成，保证这个字符串的每个前缀中 `L` 的数量大于 `R` 的数量。 第三行输入一个长度为 $N$ 的字符串, 表示每个拖拉机是否特殊。 接下来 $Q$ 行输入两个整数 $a$ 和 $b$, 表示一次查询。

对于每一组数据，一行两个数，表示答案。

### 样例 $1$ 解释 $8$ 个拖拉机的时间间隔，按顺序，是 $[1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16]$。 对于第四个查询, 第 $1$ 台和第 $5$ 台拖拉机之间有三条最短路径: $1 \rightarrow 2 \rightarrow 5$, $1 \rightarrow 3 \rightarrow 5$, 和 $1 \rightarrow 4 \rightarrow 5$。这些最短路径的长度都为 $2$。 另外, 拖拉机 $1,2,3,4,5$ 都是前面提到的三条最短路径之一的一部分, 由于 $1,2,4,5$ 是特殊的，因此有 $4$ 台特殊拖拉机，这样存在至少一条包含拖拉机 $1$ 到 $5$ 的最短路径。 - 数据点 $2-3$： $N,Q \le 5000$ - 数据点 $4-7$： 最多 $10$ 台特别的拖拉机。 - 数据点 $8-16$： 没有额外的约束。 翻译提供者：[shuqiang](https://www.luogu.com.cn/user/685964)