AT_joisc2017_f 鉄道旅行 (Railway Trip)

#「JOISC 2017 Day 2」火车旅行 **译者水平有限，跪求各位大佬提供更好的译文** **题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day2 T3「[鉄道旅行](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2.pdf)（[Railway Trip](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2-en.pdf)）」** 某条铁路线（非环线）有 $N$ 站，依次编号为 $1\ldots N$。这条线路上跑着 $K$ 类列车，编号为 $1\ldots K$。每种列车都是双向运行的。 这条铁路线上的每个车站都有个旅客流量，旅客流量是一个 $\le K$ 的正整数。车站 $i(1\le i\le N)$ 的旅客流量为 $L_i$，$L_1=L_N=K$。 第 $j$ 类列车 $(1\le j\le N)$ 在且只在旅客流量 $\ge j$ 的车站停车。 现有 $Q$ 名旅客，依次编号为 $1\ldots Q$，旅客 $k(1\le k\le Q)$ 的起点是车站 $A_k$，终点是 $B_k$ $(1\le A_k, B_k\le N)$。假设这些旅客只能靠这条铁路线移动。 对于每个旅客，求这名旅客的途中至少要**停几次站**（不含该旅客的起终点站）。保证同一名旅客的起点与终点不同。允许走回头路。

无

无

对于所有数据，$2\le N\le 10^5, 1\le K\le N, 1\le Q\le 10^5, 1\le L_i\le K(1\le i\le N), 1\le A_k, B_k\le N, A_k\not=B_k(1\le k\le Q)$。 感谢 Planet6174 提供的翻译