比赛场次 574
比赛名称 4043级2023省选模拟赛6
比赛状态 已结束比赛成绩
开始时间 2023-03-28 08:00:00
结束时间 2023-03-28 12:00:00
开放分组 全部用户
注释介绍 好题,深入交流
题目名称 Tractor Paths
输入输出 tuolapath.in/out
时间限制 4000 ms (4 s)
内存限制 512 MiB
测试点数 15 简单对比
用户 结果 时间 内存 得分
Gravatarop_组撒头屯 AAATTTTTTTTTTTT 49.568 s 19.95 MiB 20
Gravatarムラサメ AWWWWWWWWWWWWWW 0.000 s 0.00 MiB 6

Tractor Paths

★★★☆   输入文件:tuolapath.in   输出文件:tuolapath.out   简单对比
时间限制:4 s   内存限制:512 MiB

【题目描述】

农夫约翰有 $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$.