3864. [USACO23 Jan Platinum] Tractor Paths

【题目描述】

农夫约翰有 $N$ 台拖拉机，其中第 $i$ 台拖拉机的活动区间为 $[l_i,r_i]$。

拖拉机活动区间满足：所有左端点 $l_1<l_2<…<l_N$，所有右端点 $r_1<r_2<…<r_N$。

这些拖拉机中有一些是特殊拖拉机（具体哪些特殊，会在输入给出）。

如果 $[l_i,r_i]$ 和 $[l_j,r_j]$ 相交，则称两台拖拉机 $i$ 和 $j$ 相邻，农夫约翰可以从拖拉机 $i$ 直接换乘至拖拉机 $j$（反过来也可以）。

本题 $2N$ 个区间端点的位置不存在重合。

两台拖拉机 $a$ 和 $b$ 之间的路径由一系列换乘组成，具体可以表示为一个拖拉机序列，序列中的第一台拖拉机为 $a$，最后一台拖拉机为 $b$，且序列中的每两台连续的拖拉机都是相邻的。

保证拖拉机 $1$ 和拖拉机 $N$ 之间存在路径。

一条路径的长度等于该路径中换乘的次数（或者说，拖拉机序列中拖拉机的数量减一）。

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

$\bullet$ 从拖拉机 $a$ 到拖拉机 $b$ 的最短路径的长度。

$\bullet$ 满足要求的特殊拖拉机数量。要求：至少存在一条从 $a$ 到 $b$ 的最短路径中包含该特殊拖拉机。

【输入格式】

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

第二行包含一个长度为 $2N$ 的字符串，字符串由 $N$ 个 $L$ 和 $N$ 个 $R$ 组成，表示构成 $N$ 个活动区间的 $2N$ 个左右端点的相对位置顺序。保证对于这个字符串的每个真前缀（该字符串除自身外的其他前缀），其包含的 $L$ 的数量都大于其包含的 $R$ 的数量。

第三行包含一个长度为 $N$ 的 $01$ 串，对于其中的第 $i$ 个字符，如果为 $1$，则表示第 $i$ 台拖拉机是特殊拖拉机，如果为 $0$，则表示第 $i$ 台拖拉机不是特殊拖拉机。

接下来 $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输出】

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

【样例1说明】

不妨设 $16$ 个端点从左到右的位置依次为 $1 \sim 16$。

则 $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$。

【样例2】

点击下载样例2 

【数据规模与约定】

测试点 $2−3: N,Q≤5000$;

测试点 $4−7:$ 最多有 $10$ 特殊拖拉机.

对于 $100\%$ 的数据，$2≤N≤2×10^5,1≤Q≤2×10^5，1≤a<b≤N$.