题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1553

Description

Give you a sequence of n numbers, and a number k you should find the max length of Good subsequence. Good subsequence is a continuous subsequence of the given sequence and its maximum value - minimum value<=k. For example n=5, k=2, the sequence ={5, 4, 2, 3, 1}. The answer is 3, the good subsequence are {4, 2, 3} or {2, 3, 1}.

Input

There are several test cases.
Each test case contains two line. the first line are two numbers indicates n and k (1<=n<=10,000, 1<=k<=1,000,000,000). The second line give the sequence of n numbers a[i] (1<=i<=n, 1<=a[i]<=1,000,000,000).
The input will finish with the end of file.

Output

For each the case, output one integer indicates the answer.

Sample Input

Sample Output

3

1

Hint

Source

题意：

　　给你一个n个数，在这些数里面找一段连续区间，这个区间需要满足这个区间里的最大值-最小值 <= k。找出最大的区间长度。

题解：

　　拿到题的时候，就想到RMQ来找区间最值，二分长度找最大值。

　　然后队伍分工合作，一个人写二分，我写RMQ。一不小心写错了一个点wa了一次，QAQ。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 #define eps 0.0000001

 #define LNF (1<<60)

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const int mod = 1e9+;

 LL st_max[][maxn], st_min[][maxn];

 LL A[maxn];

 void RMQ_init(int n){

     for(int i=;i<n;i++)    st_max[][i]=st_min[][i]= A[i];

     for(int j = ;(<<j) <= n;j++){

         int k = <<(j-);

         for(int i=;i+k<n;i++){

             st_max[j][i] = max(st_max[j-][i], st_max[j-][i+k]);

             st_min[j][i] = min(st_min[j-][i], st_min[j-][i+k]);

         }

     }

 }

 LL RMQ(int a, int b){

     int dis = abs(b-a) + ;

     int k;

     for(k=;(<<k)<=dis;k++);

     k--;

 //    printf("%lld %lld\n", max(st_max[k][a], st_max[k][b-(1<<k)+1]), min(st_min[k][a], st_min[k][b-(1<<k)+1]));

     return max(st_max[k][a], st_max[k][b-(<<k)+])-min(st_min[k][a], st_min[k][b-(<<k)+]);

 }

 int test(int len, int n, int k)

 {

     for(int i = len-; i<n; i++){

         if(RMQ(i-len+, i)<=1LL*k)

             return ;

     }

     return ;

 }

 int main()

 {

 #ifdef LOCAL

     freopen("input.txt", "r", stdin);

 //      freopen("output.txt", "w", stdout);

 #endif // LOCAL

     int n, k;

     while(~scanf("%d%d", &n, &k)){

         ms(st_max, );

         ms(st_min, );

         ms(A, );

         for(int i=;i<n;i++) scanf("%lld", &A[i]);

         RMQ_init(n);

 //        printf("%lld\n", RMQ(0, n-1));

         int l = , r = n+;

         int mid, ans;

         while(l<r){

             mid = (l+r)/;

             if(test(mid, n, k)){

                 ans = mid;

                 l = mid+;

             }

             else

                 r = mid;

         }

         printf("%d\n", ans);

     }

     return ;

 }

模板题。XD

巴特西

CSU 1553 Good subsequence（RMQ问题 + 二分）