板子

 1 #include"bits/stdc++.h"
 2 using namespace std;
 3 
 4 int n,k;
 5 int dp[3000006][23];
 6 int dp2[3000006][23];
 7 
 8  int query(int l,int r,int type)
 9 {
10    int ss=log2(r-l+1);
11    if (type) return max(dp[l][ss],dp[r-(1<<ss)+1][ss]);  // r-(1<<ss)  !!+1
12    else return min(dp2[l][ss],dp2[r-(1<<ss)+1][ss]);
13 }
14 
15 
16  int check(int mid)
17 {
18    for (int i=1;i+mid-1<=n;i++)
19    {
20       if (1ll*abs(query(i,i+mid-1,1)-query(i,i+mid-1,0))<=1LL*k)return 1; // i ,i+mid-1(!!<--)
21    }
22    return 0;
23 }
24 int main()
25 {
26     //cout<<(int)pow(2,22);
27     scanf("%d%d",&k,&n);
28     for (int i=1;i<=n;i++)scanf("%d",&dp[i][0]),dp2[i][0]=dp[i][0];
29     for (int i=1;i<=21;i++)
30     {
31        for (int j=1;j+(1<<i)-1<=n;j++)
32        {
33           dp[j][i]=max(dp[j+(1<<(i-1))][i-1],dp[j][i-1]);//j+(1<<(i-1))
34           dp2[j][i]=min(dp2[j+(1<<(i-1))][i-1],dp2[j][i-1]);
35        }
36     }
37 
38    // cout<<query(4,7,1);
39 
40     int l=1,r=n; int ans ;
41     while (l<=r)
42     {
43       int mid = l+r>>1;   //cout<<mid<<endl;
44       if (check(mid))ans=mid,l=mid+1;else r=mid-1;
45     }
46 
47     cout<<ans;
48 }