题解：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