#P5928. [Usaco2023 Jan]Tractor Paths P
[Usaco2023 Jan]Tractor Paths P
题目描述
本题源比赛时限为 秒,内存限制为 MB。
Farmer John 有 台拖拉机,第 台只能在闭区间 内使用。左端点和右端点分别严格递增,即 、。有些拖拉机是特殊的。
若两台不同拖拉机的区间相交,就可以从其中一台换到另一台。从 到 的路径由若干次这样的换乘组成,路径长度等于换乘次数。保证拖拉机 与 之间存在路径。
对每次给定的 ,求从 到 的最短路径长度,以及有多少台不同的特殊拖拉机出现在至少一条这样的最短路径上。若端点是特殊拖拉机,也计入。
输入格式
第一行两个整数 ,满足 、。
第二行是长度为 的字符串,由 L 和 R 组成,按照端点从小到大的顺序列出端点类型。第 个 L 和第 个 R 分别对应第 台拖拉机的左右端点。每个非空真前缀中的 L 都多于 R。
第三行是长为 的二进制字符串,第 位为 1 当且仅当第 台拖拉机是特殊的。
之后 行,每行两个整数 ()。
输出格式
每次询问输出一行,依次写出所求的两个整数,以空格分隔。
样例 #1
样例输入 #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
拖拉机的区间依次为 、、、、、、、。第 次询问的三条最短路径从 出发,分别经过 、 或 ,到达 。最短路径长度是 ,这些路径一共经过了 、、、 四台特殊拖拉机。
测试点性质
- 测试点 2–3 满足 。
- 测试点 4–7 最多有 台特殊拖拉机。
- 测试点 8–16 无额外限制。