#PU1284. USACO 2023 January Contest, Platinum — Problem 1. Tractor Paths

    ID: 1539 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan23来源:usaco.orgscoring:equal_test_cases并查集

USACO 2023 January Contest, Platinum — Problem 1. Tractor Paths

USACO 2023 January Contest, Platinum — Problem 1. Tractor Paths

题目描述

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 NN (2≤N≤2⋅1052\le N\le 2\cdot 10^5) tractors, where the iith tractor can only be used within the inclusive interval [ℓi,ri][\ell_i,r_i]. The tractor intervals have left endpoints ℓ1<ℓ2<⋯<ℓN\ell_1<\ell_2<\dots<\ell_N and right endpoints r1<r2<⋯<rNr_1<r_2<\dots<r_N. Some of the tractors are special. Two tractors ii and jj are said to be adjacent if [ℓi,ri][\ell_i,r_i] and [ℓj,rj][\ell_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 QQ (1≤Q≤2⋅1051\le Q\le 2\cdot 10^5) queries, each specifying a pair of tractors aa and bb (1≤a<b≤N1\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.

数据范围

Inputs 2-3: N,Q≤5000N,Q\le 5000 Inputs 4-7: There are at most 10 special tractors. Inputs 8-16: No additional constraints. Problem credits: Benjamin Qi

样例

样例 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 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 $4$th query, there are three shortest paths between the $1$st and $5$th
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.