A90548.「USACO 2023.1 Platinum」Tractor Paths

题目译自 USACO 2023 January Contest, Platinum Problem 1. Tractor Paths

FJ 有 $N$ 台拖拉机，第 $i$ 台拖拉机只能在闭区间 $[l_i,r_i]$ 中使用。拖拉机区间的端点满足 $l_1<l_2<\ldots<l_N$ 且 $r_1<r_2<\ldots<r_N$。一些拖拉机是特别的。

如果 $[l_i,r_i]$ 和 $[l_j,r_j]$ 相交，则称两台拖拉机 $i$ 和 $j$ 为相邻的。FJ 可以从一台拖拉机转移到任意相邻的拖拉机上。两拖拉机 $a$ 和 $b$ 之间的路径是由一个转移序列组成的，这个序列中第一台拖拉机是 $a$，最后一台拖拉机是 $b$，且序列中每两台连续的拖拉机都是相邻的。保证存在一条从拖拉机 $1$ 到拖拉机 $N$ 的路径。路径的长度是转移的次数（或者等价地，是序列中拖拉机个数减 $1$）。

给你 $Q$ 个询问，每个询问指定了一对拖拉机 $a$ 和 $b$。对于每个询问，输出两个整数：

• 拖拉机 $a$ 和 $b$ 之间任意最短路径的长度。
• 有多少特别的拖拉机，满足至少有一条从拖拉机 $a$ 到拖拉机 $b$ 的最短路径包含它。

第一行两个整数 $N\ (2\le N\le 2\cdot 10^5)$ 和 $Q\ (1\le Q\le 2\cdot 10^5)$。

接下来一行一个长度为 $2N$ 的字符串，字符串中只包含 L 和 R 两种字符，表示排好序后的左右端点。保证对于这个字符串的所有正规前缀（不包括空串和全串），L 的个数多于 R 的个数。

接下来一行一个长为 $N$ 的二进制串，表示每台拖拉机是否是特别的。

接下来 $Q$ 行每行两个整数 $a$ 和 $b\ (1\le a<b\le N)$，表示一组询问。

对于每个询问，输出一行两个整数，整数之间用一个空格隔开。

• 2-3 组数据：$N,Q\le 5000$
• 4-7 组数据：最多有 $10$ 个特别的拖拉机
• 8-16 组数据：无附加限制