CF2152F Triple Attack
1.简化题意
给你 \(x_1,x_2,x_3,\dots,x_n\) 的不降序列，询问 \(q\) 次。
在 \([l,r]\) 内，最多选择几个元素，使得任意三个元素 \(x_i,x_j,x_k(i<j<k)\)，有 \(x_k-x_i > z\)。
有多测。
2.思路
首先有一个简单的暴力：取最开始的两个端点，然后一直选当前能选到的最小数。
简单证明：我们可以设 \(x_i + z\) 以后第一个数为 \(F_i\)，发现单调不降，故有最优左端点选法。
3.优化
显然上述做法是 \(O(nq)\) 的，考虑朝 \(i \to F_i\) 连一条边。
这样形成了一个树形结构，我们可以通过暴力求出答案。
现在问题来到了树上，我们可以处理出来倍增数组进行跳跃。
具体的，最开始我们选中 \(l,l+1\) 两个点（贪心），那么跳跃的时候，我们记下一次跳到 \(\operatorname{LCA},\operatorname{LCA + 1}\) 为一次跳跃，发现这个过程可以用倍增维护。
如果不能再进行两个点的 \(\operatorname{LCA}\) 跳跃，两个点分开跳到 \(r\) 的地方。
所以我们做两次倍增，一次给 \(\operatorname{LCA}\)，另外一次给成对的跳跃。
\(\Large \mathscr{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;
int n, k, T, val[N], q;
vector<int> g[N];
int dep[N], fa[N][25], lca[N][20], sum[N][20];
void dfs(int u, int fath) {fa[u][0] = fath;dep[u] = dep[fath] + 1;for (int i = 1; i <= 19; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];for (int e : g[u]) {if (e == fath) continue;dfs(e, u);}
}
int LCA(int x, int y) {if (dep[x] < dep[y]) swap(x, y);for (int i = 19; ~i; i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];if (x == y) return x;for (int i = 19; ~i; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];return fa[x][0];
}
void solve() {for (int i = 0; i <= n; i++) g[i].clear();cin >> n >> k;for (int i = 1; i <= n; i++) cin >> val[i];int pos = 1;for (int i = 1; i <= n; i++) {while (pos <= n && val[pos] <= val[i] + k) pos++;if (pos <= n) g[pos].push_back(i);else g[0].push_back(i);}dfs(0, 0);for (int i = 1; i < n; i++) lca[i][0] = LCA(i, i + 1), sum[i][0] = dep[i] + dep[i + 1] - 2 * dep[lca[i][0]];for (int i = 1; i <= 19; i++) {for (int j = 1; j < n; j++) {lca[j][i] = lca[lca[j][i - 1]][i - 1];sum[j][i] = sum[j][i - 1] + sum[lca[j][i - 1]][i - 1];}}cin >> q;for (int i = 1; i <= q; i++) {int l, r;cin >> l >> r;if (l == r) {cout << 1 << '\n';continue;}if (r == l + 1) {cout << 2 << '\n';continue;}int ans = 0;for (int i = 19; ~i; i--) {if (lca[l][i] && lca[l][i] <= r) {ans += sum[l][i];l = lca[l][i];}}if (l == r) {cout << ans + 1 << '\n';continue;}int L = l, R = l + 1;for (int i = 19; ~i; i--) {if (fa[L][i] && fa[L][i] <= r) L = fa[L][i];if (fa[R][i] && fa[R][i] <= r) R = fa[R][i];}cout << ans + dep[l] - dep[L] + 1 + dep[l + 1] - dep[R] + 1 << '\n';}
}
int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> T;while (T--) solve();return 0;
}