06709. USACO·拖拉机路径 未做

注意：本题的时限为 4 秒，是默认时限的两倍；内存限制为 512MB，是默认限制的两倍。

Farmer John 有 $N$（$2\le N\le 2\cdot 10^5$）台拖拉机，其中第 $i$ 台只能在闭区间 $[{\ell }_i,r_i]$ 内使用。这些拖拉机区间的左端点满足 ${\ell }_1<{\ell }_2<\cdots <{\ell }_N$，右端点满足 $r_1<r_2<\cdots <r_N$。其中一些拖拉机是特殊的。

如果 $[{\ell }_i,r_i]$ 与 $[{\ell }_j,r_j]$ 相交，则称拖拉机 $i$ 与拖拉机 $j$ 相邻。Farmer John 可以从一台拖拉机转移到任意一台与它相邻的拖拉机。拖拉机 $a$ 与拖拉机 $b$ 之间的一条路径是一个转移序列：序列中的第一台拖拉机是 $a$，最后一台是 $b$，且序列中相邻的两台拖拉机都是相邻的。保证拖拉机 $1$ 与拖拉机 $N$ 之间存在路径。一条路径的长度是其中转移的次数（等价于路径中拖拉机的台数减一）。

给定 $Q$（$1\le Q\le 2\cdot 10^5$）个询问，每个询问指定一对拖拉机 $a$ 和 $b$（$1\le a<b\le N$）。对于每个询问，输出两个整数：

• 拖拉机 $a$ 到拖拉机 $b$ 的任意一条最短路径的长度；
• 满足「从拖拉机 $a$ 到拖拉机 $b$ 存在至少一条经过它的最短路径」的特殊拖拉机的数量。

第一行包含 $N$ 和 $Q$。

接下来一行包含一个长度为 $2N$ 的、由 L 和 R 组成的字符串，按排序后的顺序表示左、右端点。保证该字符串的每个真前缀中，L 的数量都多于 R 的数量。

接下来一行包含一个长度为 $N$ 的 01 串，表示每台拖拉机是否特殊。

接下来 $Q$ 行，每行包含两个整数 $a$ 和 $b$，表示一个询问。

对于每个询问，用空格分隔输出这两个量。

【样例解释】

这 $8$ 个拖拉机的区间依次为 $[1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16]$。

对于第 $4$ 个询问，第 $1$ 台与第 $5$ 台拖拉机之间有三条最短路径：$1$ 到 $2$ 到 $5$、$1$ 到 $3$ 到 $5$，以及 $1$ 到 $4$ 到 $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：无附加限制。