P9019 [USACO23JAN] Tractor Paths P

题目描述

注意：这个问题的时间限制是4秒，内存限制是512MB，是默认值的两倍。

农民约翰有 $N (2 \le N \le 2 \cdot 10^5)$ 台拖拉机, 其中第 $i$ 台拖拉机只能在序列 $[l_i,r_i]$ 内使用。拖拉机有左端点 $l_1<l_2<\cdots <l_N$ 和右端点 $r_1<r_2< \cdots <r_N$. 有一些拖拉机是特别的。

如果 $[l_i,r_i]$ 和 $[l_j,r_j]$ 相交，则两台拖拉机 $i$ 和 $j$ 是相邻的。 约翰可以从一辆拖拉机转移到任何相邻的拖拉机上。两台拖拉机 $a$ 和 $b$ 之间的路径由一个传输序列组成，这样序列中的第一个拖拉机是 $a$，序列中的最后一个拖拉机是 $b$，并且序列中的每两个连续的拖拉机相邻。 保证拖拉机 $1$ 和 拖拉机 $N$ 之间有一条路径。路径的长度是转移的数量 (或等价地，其中拖拉机的数量减去 $1$)。

给定 $Q (1 \le Q \le 2 \cdot 10^5)$ 组询问，每次给定 $a$ 和 $b (1 \le a<b \le N)$。 对于每组询问，你需要回答两个问题：

• $a$ 到 $b$ 的最短路径。
• 在保证传送次数的最少的情况下，有多少个特殊拖拉机的区间可能被某条最短路经过。

输入格式

第一行输入两个整数 $N$ 和 $Q$，表示有 $N$ 台拖拉机和 $Q$ 次询问。

第二行输入一个长度为 $2N$ 的字符串，由大写字母 L 和 R 组成，保证这个字符串的每个前缀中 L 的数量大于 R 的数量。

第三行输入一个长度为 $N$ 的字符串, 表示每个拖拉机是否特殊。

接下来 $Q$ 行输入两个整数 $a$ 和 $b$, 表示一次查询。

输出格式

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

输入输出样例 1

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

1 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2

说明/提示

样例 $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