#P3085. [USACO23JAN] Tractor Paths P

[USACO23JAN] Tractor Paths P

题目描述

Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default.

Farmer John has N(2N2105)N (2 \le N \le 2 \cdot 10^5) tractors, where the ii-th tractor can only be used within the inclusive interval [li,ri][l_i,r_i]. The tractor intervals have left endpoints l1<l2<<lNl_1<l_2<\cdots <l_N and right endpoints r1<r2<<rNr_1<r_2< \cdots <r_N. Some of the tractors are special.

Two tractors ii and jj are said to be adjacent if [li,ri][l_i,r_i] and [lj,rj][l_j,r_j] intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors aa and bb consists of a sequence of transfers such that the first tractor in the sequence is aa, the last tractor in the sequence is bb, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor 11 and tractor NN. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).

You are given Q(1Q2105)Q (1 \le Q \le 2 \cdot 10^5) queries, each specifying a pair of tractors aa and b(1a<bN)b (1 \le a<b \le N). For each query, output two integers:

  • The length of any shortest path between tractor aa to tractor bb.
  • The number of special tractors such that there exists at least one shortest path from tractor aa to tractor bb containing it.

输入格式

The first line contains NN and QQ.

The next line contains a string of length 2N2N consisting of Ls and Rs, representing the left and right endpoints in sorted order. It is guaranteed that for each proper prefix of this string, the number of Ls exceeds the number of Rs.

The next line contains a bit string of length NN, representing for each tractor whether it is special or not.

The next QQ lines each contain two integers aa and bb, specifying a query.

输出格式

For each query, the two quantities separated by spaces.

题目大意

nn 个区间,第 ii 个区间为 [li,ri][l_i,r_i]。保证 l1<l2<<lnl_1<l_2<\cdots<l_nr1<r2<<rnr_1<r_2<\cdots<r_n。其中一部分区间是特殊的,输入会给定。

如果第 ii 个区间和第 jj 个区间相交,那么 i,ji,j 之间有一条边。保证 1,n1,n 联通。

给定 QQ 组询问,每次给定 a,ba,b 满足 1a<bn1\le a < b\le n,你需要回答 aabb 至少要经过多少条边,以及有多少个特殊区间对应的点,使得这个点可能在 aabb 的最短路径上。

n,Q2×105n,Q\le 2\times 10^5

输入格式

第一行包含两个整数 NNQQ

下一行包含一个长度为2N2N的字符串,由L和R组成,按排序顺序表示左端点和右端点。可以保证,对于该字符串的每个适当前缀,L的数量都超过R的数量。

下一行包含一个长度为NN的位字符串,表示每台拖拉机是否特殊。

接下来的QQ行分别包含两个整数aabb,表示一个查询。

输出格式

对于每个查询,用空格分隔的两个输出。

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 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2

提示

Explanation for Sample 1

The 88 tractor intervals, in order, are [1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16][1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16].

For the 4th query, there are three shortest paths between the 1st and 5th tractor: 11 to 22 to 55, 11 to 33 to 55, and 11 to 44 to 55. These shortest paths all have length 22.

Additionally, every tractor 1,2,3,4,51,2,3,4,5 is part of one of the three shortest paths mentioned earlier, and since 1,2,4,51,2,4,5 are special, there are 44 special tractors such that there exists at least one shortest path from tractor 11 to 55 containing it.

Scoring

  • Inputs 232-3: N,Q5000N,Q \le 5000
  • Inputs 474-7: There are at most 1010 special tractors.
  • Inputs 8168-16: No additional constraints.