8171: USACO 2023 January Contest, Platinum Problem 1. Tractor Paths
[Creator : ]
Description
Farmer John has $N\ (2≤N≤2⋅10^5)$ tractors, where the i-th tractor can only be used within the inclusive interval $[ℓ_i,r_i]$. The tractor intervals have left endpoints $ℓ_1<ℓ_2<⋯<ℓ_N$ and right endpoints $r_1<r_2<⋯<r_N$. Some of the tractors are special.
Two tractors i and j are said to be adjacent if $[ℓ_i,r_i]$ and $[ℓ_j,r_j]$ intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors a and b consists of a sequence of transfers such that the first tractor in the sequence is a, the last tractor in the sequence is b, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor 1 and tractor N. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).
You are given $Q\ (1≤Q≤2⋅10^5)$ queries, each specifying a pair of tractors a and b (1≤a<b≤N). For each query, output two integers:
Two tractors i and j are said to be adjacent if $[ℓ_i,r_i]$ and $[ℓ_j,r_j]$ intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors a and b consists of a sequence of transfers such that the first tractor in the sequence is a, the last tractor in the sequence is b, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor 1 and tractor N. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).
You are given $Q\ (1≤Q≤2⋅10^5)$ queries, each specifying a pair of tractors a and b (1≤a<b≤N). For each query, output two integers:
- The length of any shortest path between tractor a to tractor b.
- The number of special tractors such that there exists at least one shortest path from tractor a to tractor b containing it.
Input
The first line contains N and Q.
The next line contains a string of length 2N 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 N, representing for each tractor whether it is special or not.
The next Q lines each contain two integers a and b, specifying a query.
The next line contains a bit string of length N, representing for each tractor whether it is special or not.
The next Q lines each contain two integers a and b, specifying a query.
Output
For each query, the two quantities separated by spaces.
Sample 1 Input
8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
Sample 1 Output
1 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2
The 8 tractor intervals, in order, are [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: 1 to 2 to 5, 1 to 3 to 5, and 1 to 4 to 5. These shortest paths all have length 2.
Additionally, every tractor 1,2,3,4,5 is part of one of the three shortest paths mentioned earlier, and since 1,2,4,5 are special, there are 4 special tractors such that there exists at least one shortest path from tractor 1 to 5 containing it.