概述：交互库给你一棵树，你需要在所有询问开始前给交互库两个排列 $p1,p2$，随后交互库每次生成一个排列 $a$ 与两个点 $u,v$，要让你求树上 $u,v$ 路径间 $a_i$ 的 $mex$，你可以询问 $5$ 次两个排列上的区间最小值。$n\times q\le3\times 10^6$。

解法：对于排列，显然有 $mex_{i\in S}a_i = \min_{i\not \in S}a_i$，因此我们可以将原问题转为询问路径补集的 $\min$。路径补集刻画为比 $lca$ 的 $dfn$ 还小的点，比 $\max(dfn_u,dfn_v)$ 还大的点，以及路径上所有点左右挂着的点。

先让 $p_1$ 为原 $dfn$ 序，对上述两种点询问，发现第二种点包括了 $lca \to v$ 链上的挂在右边的点。启发我们让 $p2$ 为反着的 $dfn$，询问 $>dfn_u$ 的点，这样也包括了 $lca\to u$ 链上挂在左边的点。

考虑剩下的点，容易发现 $lca\to u$ 的右边的点显然满足 $dfn_u<dfn_i<dfn_p$，其中 $p$ 是 $lca\to v$ 链上的第二个点。因此询问一次即可。 $lca\to v$ 同理。

概述：

$n$ 个人赛跑，第 $i$ 个人有一个速度 $t_i$ 表示他走单位距离需要的时间。第 $i$ 场比赛为编号 $[1,i]$ 的人参加。

赛跑场地始终相同，都有 $m$ 个存档点，坐标依次为 $s_i$。最后一个存档点是终点。初始时所有人从 $0$ 出发，每次有人遇到存档点时其他所有人都会传送回自己的上一个存档点（同时则编号小的视为先到）。到终点的人不会被传送。

求问每场比赛的总传送次数。$n,m,s_m\le 1.5\times 10^5,t_i\le 10^9$。

思路：

考虑传送事实上只是某个人前进了一个存档点，每两次传送之间互不影响。

对于两个人 $i,j$，若 $i$ 更快则 $i$ 一定让 $j$ 传送了 $m$ 次。因此我们答案至少是 $\frac {i(i-1)} 2$。

再考虑更多传送的部分，事实上是较慢的 $j$ 由于走的距离短导致了 $i$ 的传送。那么这个时候我们完全可以视为 $i$ 在走最长的一段（总时间消耗最大），而 $j$ 在走某个前缀最大值（前一个时间比后一个长，那么走完前一个后必然会马上走下一个）。再根据上面说的传送互不影响，我们发现最终答案就是所有 $(i,j)$ 传送次数的和。

由此得到一个看似 $O(n^2m)$ 的算法，暴力枚举 $(i,j)$，再根据前缀 $\max$ 们暴力判断 $j$ 会走到哪里。但是发现各段长总和仅有 $1.5\times 10^5$ 种，因此前缀 $\max$ 数量仅 $\sqrt V$ 种。做到 $O(n^2\sqrt V)$。

优化是显然的：考虑每次加入一个人 $i$，对他之前的人与他的快慢关系讨论。$i$ 较快则是枚举前缀 $\max$，分成 $\sqrt V$ 个区间询问。容易想到一个 $\sqrt V\log n$ 做法：区间询问用树状数组维护，而找到区间用二分。前半部分经典平衡规划；后半部分由于前缀 $\max$ 数量少，区间左右端点单增，因此双指针预处理即可。$i$ 较慢时是对偶平衡规划问题，不细讲。至此本题做到 $O(n\sqrt n)$。