题目描述

Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default.

Farmer John has $N (2 \le N \le 2 \cdot 10^5)$ tractors, where the $i$-th tractor can only be used within the inclusive interval $[l_i,r_i]$. The tractor intervals have left endpoints $l_1<l_2<\cdots <l_N$ and right endpoints $r_1<r_2< \cdots <r_N$. Some of the tractors are special.

Two tractors $i$ and $j$ are said to be adjacent if $[l_i,r_i]$ and $[l_j,r_j]$ intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors $a$ and $b$ consists of a sequence of transfers such that the first tractor in the sequence is $a$, the last tractor in the sequence is $b$, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor $1$ and tractor $N$. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).

You are given $Q (1 \le Q \le 2 \cdot 10^5)$ queries, each specifying a pair of tractors $a$ and $b (1 \le a<b \le N)$. For each query, output two integers:

• The length of any shortest path between tractor $a$ to tractor $b$.
• The number of special tractors such that there exists at least one shortest path from tractor $a$ to tractor $b$ containing it.

输入格式

The first line contains $N$ and $Q$.

The next line contains a string of length $2N$ consisting of Ls and Rs, representing the left and right endpoints in sorted order. It is guaranteed that for each proper prefix of this string, the number of Ls exceeds the number of Rs.

The next line contains a bit string of length $N$, representing for each tractor whether it is special or not.

The next $Q$ lines each contain two integers $a$ and $b$, specifying a query.

输出格式

For each query, the two quantities separated by spaces.

题目大意

题目描述

注意：这个问题的时间限制是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$ 个拖拉机的时间间隔，按顺序，是 $[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

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

提示

Explanation for Sample 1

The $8$ tractor intervals, in order, are $[1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16]$.

For the 4th query, there are three shortest paths between the 1st and 5th tractor: $1$ to $2$ to $5$, $1$ to $3$ to $5$, and $1$ to $4$ to $5$. These shortest paths all have length $2$.

Additionally, every tractor $1,2,3,4,5$ is part of one of the three shortest paths mentioned earlier, and since $1,2,4,5$ are special, there are $4$ special tractors such that there exists at least one shortest path from tractor $1$ to $5$ containing it.

Scoring

• Inputs $2-3$: $N,Q \le 5000$
• Inputs $4-7$: There are at most $10$ special tractors.
• Inputs $8-16$: No additional constraints.