【题目】IOI2018 狼人

题目大意

给出一张$N$个点$M$条边的无向图，保证图连通。你有$Q$个行程，第$i$个行程的起点是$S_i$，终点是$E_i$。在每个行程开始时你必须是人形，在每个行程结束时你必须是狼形，且途中只能在$[L_i,R_i]$内的某个点变身。问每次行程能否完成。

$N⩽200000$，$M⩽400000$，$Q⩽200000$。

---

思路

前置芝士：Kruskal重构树，二维数点。

每个可行的行程可以表示成：$S_i\to X\to E_i$，其中$L_i⩽X⩽R_i$。

以$X\to E_i$这一部分路径为例。这条路径可以等价成$E_i\to X$。我们需要找出从$E_i$出发，经过的点的编号最大不超过$R_i$，能够到达的所有点，这些点都有可能成为$X$。路径上的最大点权尽可能小，假装容易想到最小生成树。但是生成树处理的是边权，这里要把点权转到边权：经过一条边时，一定会经过这条边的两个端点，因此可以把边权设为两个端点编号的最大值。然后建一棵传说中的Kruskal重构树。为了后面讨论方便，叶子结点的点权设为本身的编号。于是原图中两点路径上的最大点权的最小值就是树中两点的LCA的点权。并且，由于连通块是按权值从小到大合并的，树中非根节点的点权一定不会超过父亲的点权。

在重构树中找到点$S_i$，倍增找到其祖先中深度最浅、点权不超过$R_i$的点，则点$X$必须在以该点为根的子树内。

同理，需要找出从$S_i$出发，经过的点的编号最小不低于$L_i$，能够到达的所有的点：边权取两个端点的点权的最小值，求最大生成树，在重构树上倍增，找到深度最浅、点权不低于$L_i$的点，则点$X$必须在以该点为根的子树内。

于是点$X$在两棵重构树上的DFS序各有一个范围，以每个点分别在两棵树上的DFS序为横纵坐标，转换成二维数点问题。