写在前面
最近在学倍增，被紫题虐哭后又来尝试这个蓝题，没想到实现起来也有一定的难度。
看不懂大佬们的题解和代码，所以打算写一个比较易懂的题解。
其实思路与第一篇题解类似，但是它讲的太笼统了。就像 "经" 需要 "传" 来解释一样，所以我打算将这种思路写的更详细一些，让有一定倍增基础的同志们可以看懂。
前置知识
题目大意（戳这里查看原题）
- 给定 n 个点，m 条路线。
- 给定一个整数 K，表示乘车点离始发点的最远距离。
- 对于每条路线，给定 \langle A_{i},B_{i} \rangle 表示路线的起点和终点。
注意： A_{i}，B_{i} 相对大小关系不确定，可分别表示正向和反向。
- 接下来有 Q 次询问。
- 对于每次询问，给定 \langle S_{i},T_{i} \rangle 表示询问的起点和终点。求是否能够通过换乘从 S_{i} 到达 T_{i}，如果可以输出最少换乘次数。
- 无解输出 -1。
正文
就我目前的经验来看，凡是需要多次无序询问或者重复多次处理一张图时，大概率是需要用到倍增的。
简单说一下原因：当我们要多次处理（或询问）一张图时（假设 n 个点），那么如果一次次遍历，复杂度很可能是 O(n^2) 或更高，在动不动就 n >10^5 的数据下肯定是不行的，而倍增可以将每次遍历降到 \log{n} 级别，显然是一种很有效的优化方法。
然后我们以倍增作为思考切入点，再回到这题。我们可以先把数据(样例 3)手出来观察一下：
以 \text{start}=2，\text{end}=6 为例， 我们要从 2 号点走到 6 号点，则需要在 2 号点坐二号线于 4 号点下车，再从 4 号点坐四号线于 6 号点下车。需要坐 2 条线路。
一看就非常想上倍增。满足多次无序询问，而且这个图很大，但是感觉又不老好实现的，我们继续思考。
接下来从倍增两个基本步骤入手：预处理、询问。
预处理
考虑倍增。终点可以在起点的左边，也可以在起点的右边。所以左右都要考虑到。我们用 le(i,k)、ri(i,k) 分别代表以第 i 个点为起点，乘坐 2^k 条路线所能到达的最远左端点、右端点。
可以证明：此时第 i 点乘坐 2^k 条路线能到达的所有点均属于区间 [le_{i,k} , ri_{i,k}]，且该区间内没有点不能被 i 到达。（可以这么想：既然能到达最远，则一定有一条路线连接起点和最远点，那么中间的这些点只要提前下车就行了。上车有限制，但是下车没有）。
接下来想一下如何递推倍增式。对于 2^k 次换乘，一定保证 le(i,k-1) ≥ le(i,k) 且 ri(i,k-1) ≤ ri(i,k) 才有意义。通过我们刚才的推论，在 [le_{i,k-1} , ri_{i,k-1}] 中的所有点都可以被 i 点到达，则我们可以在 i 乘坐一条路线时选择到达其中的一点 j，通过 j 的 le(j,k-1) 和 ri(j,k-1) 来扩展点 i 的情况。式子就很容易得出了：
$ri(i,k) = \max(ri(i,k),ri(j,k-1))$；
其中 $j \in [ le_{i,k-1} , ri_{i,k-1} ]$。
考虑一般情况: 显然递推要使用一个区间内的最值，这就成为了一个 RMQ 问题，那么一个个枚举显然是很耗时的。 我们可以用**线段树**来优化这个过程。 （之后，我们可以想想是用一颗线段树滚动，还是要建很多颗线段树 ? ）
------------
现在还有一个很~~棘手~~的问题，就是初始的 $le(i,0)$，$ri(i,0)$ 如何得出？ 我是没想出如何用线段树， 但我们可以使用一个稍加修改的**单调队列**求出。（正是别的题解对这块一笔带过才让我下决心写这篇题解）
现在考虑**单调队列**，首先，队列要装**路线**（这样处理出终点最远的路线，计算答案时找到这个终点即可），所以大小应该是 $m$ 个。其次，需要改动的地方就是我们要在枚举路线的同时更新我们的点。 这个想想应该也能明白，我们枚举每个点，同时以这个点为参照逐渐枚举路线。
以求 $ri(i,0)$ 为例，即在队列里的路线满足起点在该点前，终点在该点后，队列中路线的终点要最右，所以这些路线按照其终点的大小在队列中满足单调递减。
**注意**：我们如果要枚举到满足这个点条件的所有路线，显然要将这些路线**按起点排序**。
------------
还有两个**小细节**：
1. $ri(i,k)$ 是向右最远的点，所以只有正向路线可能有影响；反之 $le(i,k)$ 则只受逆向路线影响。要**分开枚举**。
2. 单调队列中，如何判断一条路线是否**合法**？以求 $ri(i,0)$ 为例。对于一个路线的起点 $S$，合法满足 $i≤S+K-1$， 整理得 $S≥i-K+1$，则对于任意 $S≤i-K$ 的路线都不能满足 $i$ 是起点，是**不合法**的，应该**删去**。
------------
则预处理的总复杂度 $O(n\log^2{n}+m)$。
分别是一般情况的**线段树$+$倍增**和起始的**单调队列**。
------------
#### 询问
然后这题的难点就基本解决了。我们再来考虑一下询问如何处理。
对于一对询问 $\langle S_{i} , E_{i}\rangle$，我们尝试从 $S_{i}$ 不断向左右扩展，直到能到达的区间覆盖住了 $E_{i}$。
同时注意一下如何保证**正确性**：
可以联想一下倍增求 LCA。首先我们要倒序枚举 $k$ 保证大的先处理。 同时，LCA 在处理的时候不会让两个点跳到一起，只会跳到最近公共祖先的子节点，从而保证不会出现跳到 LCA 上面导致祖先重合的情况。 类比这个方法， 我们也可以使最后的区间 **将要但不包括 $E_{i}$**，从而避免乘坐了过多的线路。
最后我们再来考虑一下**最终的答案：**
对于一次询问，我们为了保证正确性，确保每次更新换乘点都满足**不达到，但尽可能将要到达**终点。那么当我们完成一次完整的循环处理（即从换乘 $2^k$ 次一直到换乘 $2^0$ 次后到达的点），这时记录的答案一定**不能够**使我们到达终点。可以证明，如果这个询问**有解**，**当且仅当终点 $E_{i}$ 位于最后一次到达的换乘点 $j$ 换乘一次可到达的点的范围内（$E_{i}\in [le_{j,0},ri_{j,0}]$）**。若不满足这个条件则**无解**，输出 $-1$。
如果读者不明白为什么是这个条件，我们仍然可以联想倍增求 LCA。这里我通过**反证法**给出一个**不严谨**的简单证明：
假如最后的终点 $E_{i}$ 不满足上面的条件且保证有解，则一定满足 $E_{i}\in [le_{j,k},ri_{j,k}]$，其中 $k \in [1,\lfloor\log{n}\rfloor]$。然而，我们在处理询问的循环中是从大到小枚举 $k$，则一定可以找到一个枚举的 $k$，将最后的换乘点 $j$ 更新，且满足**不达到，但将要到达**终点这个条件。前后**矛盾**。
------------
**注意：** 按照这种方法扩展也**不能只考虑起点**，而是要考虑每次换乘起点所能到达的所有点，取最优。然后又回到了令人~~欣喜~~的 RMQ 环节。我们直接枚举倍增的数组显然也不是最优的，这就突显出我们线段树的好处了，自然我们可以用处理倍增的线段树来在 $\log{n}$ 下得出当前的最优。也就回答了上面的思考，我们要建 $\lfloor\log{n}\rfloor+1$ 颗线段树，不用滚动优化。
------------
询问的复杂度 $O(q\log^2{n})$。
------------
最后的**总复杂度** $O((n+q)\log^2{n}+m)$。
## 代码
##### 对一些变量名的解释（~~我觉得是比较正常的~~）
- $le(i,k)$ 表示向左最远到达点的倍增数组
- $ri(i,k)$ 表示向右最远到达点的倍增数组
- $up(i)$，$cnt\_up$ 用于记录正向路径（取 $\text{up}$ 上行意）
- $down(i)$，$cnt\_down$ 用于记录逆向路径（取 $\text{down}$ 下行意）
因为要建**多颗**线段树，所以用结构体封装，开 $\text{root}=17$ 个线段树。
------------
```cpp
/* code by jjsnam 2022.4.29 */
/* Using Segment Tree */
#include <iostream>
#include <algorithm>
#include <cstring>
#define ls (id<<1)
#define rs (id<<1|1)
#define mid ((l+r)>>1)
#define u first
#define v second
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e5+5;
const int maxm=2e5+5;
int le[maxn][17],ri[maxn][17];
pii up[maxm],down[maxm];
int cnt_up,cnt_down;
int n,m,K,Q;
struct Segment_Tree{
struct Node{
int left,right;
}tr[maxn<<2];
void pushup(int id){
tr[id].left=min(tr[ls].left,tr[rs].left);
tr[id].right=max(tr[ls].right,tr[rs].right);
}
void build(int id,int l,int r,int k){
if (l==r){
tr[id].left=le[l][k];
tr[id].right=ri[r][k];
return;
}
build(ls,l,mid,k);
build(rs,mid+1,r,k);
pushup(id);
}
int query_left(int id,int l,int r,int a,int b){
if (a<=l&&r<=b){
return tr[id].left;
}
int res=1e9;
if (a<=mid) res=min(res,query_left(ls,l,mid,a,b));
if (b>mid) res=min(res,query_left(rs,mid+1,r,a,b));
return res;
}
int query_right(int id,int l,int r,int a,int b){
if (a<=l&&r<=b){
return tr[id].right;
}
int res=-1e9;
if (a<=mid) res=max(res,query_right(ls,l,mid,a,b));
if (b>mid) res=max(res,query_right(rs,mid+1,r,a,b));
return res;
}
}root[17];
void Get_start(){
for (int i=1;i<=n;i++) le[i][0]=ri[i][0]=i;
sort(up+1,up+cnt_up+1);
sort(down+1,down+cnt_down+1,greater<pii>());
/* 单调队列 O(m) */
int q[maxm],hh=1,tt=0;
/* 处理右 */
for (int i=1,j=1;i<=n;i++){
while (j<=cnt_up&&up[j].u<=i){
int r=up[j].v;
while (hh<=tt&&up[q[tt]].v<=r) tt--;
q[++tt]=j;
j++;
}
while (hh<=tt&&up[q[hh]].u<=i-K) hh++;
if (hh<=tt) ri[i][0]=max(ri[i][0],up[q[hh]].v);
}
/* init */
hh=1,tt=0;
/* 处理左 */
for (int i=n,j=1;i>0;i--){
while (j<=cnt_down&&down[j].u>=i){
int l=down[j].v;
while (hh<=tt&&down[q[tt]].v>=l) tt--;
q[++tt]=j;
j++;
}
while (hh<=tt&&down[q[hh]].u>=i+K) hh++;
if (hh<=tt) le[i][0]=min(le[i][0],down[q[hh]].v);
}
}
void init(){
Get_start();
root[0].build(1,1,n,0);
for (int k=1;k<=16;k++){
for (int i=1;i<=n;i++){
le[i][k]=root[k-1].query_left(1,1,n,le[i][k-1],ri[i][k-1]);
ri[i][k]=root[k-1].query_right(1,1,n,le[i][k-1],ri[i][k-1]);
}
root[k].build(1,1,n,k);
}
}
int query(int S,int E){
int res=0;
int l=S,r=S;
for (int k=16;k>=0;k--){
int L=root[k].query_left(1,1,n,l,r);
int R=root[k].query_right(1,1,n,l,r);
if (L<=E&&E<=R) continue;
l=L,r=R;
res+=(1<<k);
}
int L=root[0].query_left(1,1,n,l,r);
int R=root[0].query_right(1,1,n,l,r);
if (L<=E&&E<=R) return res+1;
else return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> K >> m;
for (int i=1,a,b;i<=m;i++){
cin >> a >> b;
if (a<b) up[++cnt_up]=make_pair(a,b);
else down[++cnt_down]=make_pair(a,b);
}
init();
cin >> Q;
int s,e;
while (Q--){
cin >> s >> e;
cout << query(s,e) << endl;
}
return 0;
}
```
------------
## 总结
此题的这种做法其实是 **RMQ** 问题与**倍增**的结合。
它与其他倍增题做法有一些**不同之处**：
- 最后询问不是直接使用倍增数组，而是用更新倍增数组的线段树更新答案。
可以这么理解：每一层倍增由**上一层**的线段树区间最值求得，而**这一层**的线段树初始值则是**更新后**的倍增数组。所以广义上说，我们存的**线段树也算一个倍增**。
- 本题更新倍增数组的方法也不是单一的递推，而是通过线段树优化后的区间最值递推。
------------
然后这道题就结束了！好耶（
应该还是有更优的 RMQ 做法的，但是我太弱了想不出来（
第一次写题解，可能我的表述也比较菜，如果有问题欢迎指出！