题解：CF2152F Triple Attack

一开始读成 $<z$ 然后发现是宝宝题，然而对本题做法没有任何启发。

题意等价于选一个子序列满足 $y_i-y_{i-2}>z$，因此需要按奇偶分别考虑。先考虑如果合法条件是 $y_i-y_{i-1}>z$ 的话怎么做。可以无脑离线但是对本题做法没有任何启发，令 $f_i$ 代表 $i$ 后面第一个 $x_j-x_i>z$ 的位置 $j$，则贪心地从 $l$ 开始不断跳 $f$ 直到超过 $r$ 即可，套个倍增即可维护。这里我们建树 $(i,f_i)$ 方便理解。

考虑怎么做原题，仍然贪心地选择 $y_1=l,y_2=l+1$，此时我们要分别构造两条链，理想的情况是 $y_1,y_2$ 各自跳父亲，互不影响。但实际上显然跳到 $\text{lca(}y_1,y_2)$ 时会出现问题，两条链怎么能重复呢。这个时候我们要令一条链换个位置，贪心的换成 $\text{lca}+1$ 即可。如果 $\text{lca}$ 超过了 $r$，直接分别跳两条链即可。当然不能每次暴力大跳到 $\text{lca}$ 复杂度不对，可以再套一个倍增。

具体来说，先倍增的跳 $\text{lca}$ 直到这个位置要超过 $r$ 了，然后分别两个小倍增跳两条链。复杂度 $O((n+q)\log n)$。

submission：https://codeforces.com/contest/2152/submission/341854975