思路：简单dp，用st表+单调队列维护一下。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg
using namespace std; const int N = 1e5 + ;
const int M = 1e7 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = ; int n, s, l, tot, head, rear, a[N], dp[N], stk[N], Log[N]; struct ST {
int dp[N][],ty;
void build(int n, int b[], int _ty) {
ty = _ty;
for(int i = ; i <= n; i++) dp[i][] = ty * b[i];
for(int j = ; j <= Log[n]; j++)
for(int i = ; i+(<<j)- <= n; i++)
dp[i][j] = max(dp[i][j-], dp[i+(<<(j-))][j-]);
}
int query(int x, int y) {
int k = Log[y - x + ];
return ty * max(dp[x][k], dp[y-(<<k)+][k]);
}
}mx, mn; bool check(int L, int R) {
return mx.query(L, R) - mn.query(L, R) <= s;
} int main() { for(int i = -(Log[]=-); i < N; i++)
Log[i] = Log[i - ] + ((i & (i - )) == ); memset(dp, -, sizeof(dp)); scanf("%d%d%d", &n, &s, &l);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
mx.build(n, a, ); mn.build(n, a, -); head = , rear = ;
for(int i = ; i <= n; i++) {
if(i >= l && check(, i)) {
dp[i] = ;
stk[++rear] = i;
continue;
}
while(rear >= head && !check(stk[head] + , i)) head++;
if(rear >= head && i - stk[head] >= l) {
dp[i] = dp[stk[head]] + ;
stk[++rear] = i;
}
}
printf("%d\n", dp[n]);
return ;
} /*
76 63 14
89 87 35
20 15 56
*/