意义不明的线段树解法

参考Macw这题题解的思路
首先我们得出 $O(n^2)$ 的DP状态转移方程：枚举可以够到的每个点，统计最小值，$+1$ 就行了.
然后我们注意到枚举的是连续的区间，所以我们可以用线段树来实现区间查找
因为 $m\le 5\times 10^5$，所以我选择zkw卡常树.（虽然常规线段树、树状数组也不是不行）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <memory.h>
using namespace std;
int a[500005];
int sum[1048581];
int size, depth;
void modify(int idx, int val){//O(logn)单点加 
	for(sum[idx += size] = val, idx >>= 1; idx; idx >>= 1){
		sum[idx] = min(sum[idx * 2], sum[idx * 2 + 1]);
	}
}
int query(int l, int r){//O(logn)区间加 
	int ct = 0x3f3f3f3f;
	for(l = l + size - 1, r = r + size + 1; l ^ r ^ 1; l >>= 1, r >>= 1){
		if(~l & 1) ct = min(ct, sum[l ^ 1]);
		if(r & 1) ct = min(ct, sum[r ^ 1]);
	}
	return ct;
}
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n, m, k;
	cin >> m >> n >> k;
    a[1] = 1, n++;//起始点1也可看作平台
	for(int i = 2; i <= n; i++){
		cin >> a[i];
	}
	memset(sum, 63, sizeof(sum));
	size = 1 << (depth = ceil(log2(n)) + 1e-5);
	modify(1, 0);//最开始不用跳
	for(int i = 2; i <= n; i++){
		int idx = lower_bound(a + 1, a + n + 1, a[i] - k) - a;//最远能够到的
		int ans = query(idx, i - 1) + 1;//求最小次数
		modify(i, ans);//修改
	}
	int idx = lower_bound(a + 1, a + n + 1, m - k) - a;
	int ans = query(idx, n) + 1;
	cout << (ans >= 0x3f3f3f3f ? -1 : ans);
	

	return 0;
}

这样我们就成功地把时间复杂度降至 $O(n\log n)$ 了.
好像用队列做可以降到O(n)？不管了