#P5928. [Usaco2023 Jan]Tractor Paths P

    ID: 4928 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理倍增跳转一维前缀和构造与建模交换求和顺序CF2600

[Usaco2023 Jan]Tractor Paths P

题目描述

本题源比赛时限为 44 秒,内存限制为 512512 MB。

Farmer John 有 NN 台拖拉机,第 ii 台只能在闭区间 [ℓi,ri][\ell_i,r_i] 内使用。左端点和右端点分别严格递增,即 ℓ1<ℓ2<⋯<ℓN\ell_1<\ell_2<\cdots<\ell_N、r1<r2<⋯<rNr_1<r_2<\cdots<r_N。有些拖拉机是特殊的。

若两台不同拖拉机的区间相交,就可以从其中一台换到另一台。从 aa 到 bb 的路径由若干次这样的换乘组成,路径长度等于换乘次数。保证拖拉机 11 与 NN 之间存在路径。

对每次给定的 a,ba,b,求从 aa 到 bb 的最短路径长度,以及有多少台不同的特殊拖拉机出现在至少一条这样的最短路径上。若端点是特殊拖拉机,也计入。

输入格式

第一行两个整数 N,QN,Q,满足 2≤N≤2×1052\le N\le 2\times10^5、1≤Q≤2×1051\le Q\le 2\times10^5。

第二行是长度为 2N2N 的字符串,由 L 和 R 组成,按照端点从小到大的顺序列出端点类型。第 ii 个 L 和第 ii 个 R 分别对应第 ii 台拖拉机的左右端点。每个非空真前缀中的 L 都多于 R。

第三行是长为 NN 的二进制字符串,第 ii 位为 1 当且仅当第 ii 台拖拉机是特殊的。

之后 QQ 行,每行两个整数 a,ba,b(1≤a<b≤N1\le a<b\le N)。

输出格式

每次询问输出一行,依次写出所求的两个整数,以空格分隔。

样例 #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

拖拉机的区间依次为 [1,5][1,5]、[2,10][2,10]、[3,11][3,11]、[4,12][4,12]、[6,13][6,13]、[7,14][7,14]、[8,15][8,15]、[9,16][9,16]。第 44 次询问的三条最短路径从 11 出发,分别经过 22、33 或 44,到达 55。最短路径长度是 22,这些路径一共经过了 11、22、44、55 四台特殊拖拉机。

测试点性质

  • 测试点 2–3 满足 N,Q≤5000N,Q\le5000。
  • 测试点 4–7 最多有 1010 台特殊拖拉机。
  • 测试点 8–16 无额外限制。