CSU1553 Good subsequence —— 二分 + RMQ/線段樹

題目連結： 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

5 2
5 4 2 3 1
1 1
1      

Sample Output

3
1      

題解：

之前學了RMQ，線段樹， 樹狀數組，但是一直不知道他們在哪裡能派上用場。通過這題，終于找到他們的用武之地了：區間查詢最大最小值。

解決了查詢區間最大最小值的問題，剩下的就是二分了。這裡是二分長度。

RMQ：

#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 = 10000+10;
const int mod = 1e9+7;

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

void RMQ_init(int n)
{
    for(int i = 0; i<n; i++)
    {
        st_min[i][0] = a[i];
        st_max[i][0] = a[i];
    }

    for(int j = 1; (1<<j)<=n; j++)//枚舉長度
    for(int i = 0; i+(1<<j)-1<n; i++)//枚舉起點
    {
        st_min[i][j] = min(st_min[i][j-1],st_min[i+(1<<(j-1))][j-1]);
        st_max[i][j] = max(st_max[i][j-1],st_max[i+(1<<(j-1))][j-1]);
    }
}

LL RMQ(int l, int r)//查詢
{
    int k = 0;
    while((1<<(k+1))<=r-l+1)
        k++;
    return max(st_max[l][k],st_max[r-(1<<k)+1][k]) - min(st_min[l][k],st_min[r-(1<<k)+1][k]);
}

int test(int len, int n, int k)
{
    for(int i = len-1; i<n; i++)
        if(RMQ(i-len+1, i)<=1LL*k)
            return 1;

    return 0;
}

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))
    {
        for(int i=0;i<n;i++)
            scanf("%lld", &a[i]);

        ms(st_max, 0);
        ms(st_min, 0);
        RMQ_init(n);

        int l = 1, r = n;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(test(mid, n, k))
                l = mid+1;
            else
                r = mid-1;
        }
        printf("%d\n", r);
    }
    return 0;
}
           

線段樹：

#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 1000000000000
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 10000+10;
const int mod = 1e9+7;

LL st_max[4*maxn], st_min[4*maxn];
LL a[maxn];

void build(int rt, int l, int r)
{
    if(l==r)
    {
        st_max[rt] = a[r];
        st_min[rt] = a[r];
        return;
    }

    int mid = (l+r)>>1;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    st_max[rt] = max(st_max[rt*2], st_max[rt*2+1]);
    st_min[rt] = min(st_min[rt*2], st_min[rt*2+1]);
}

//由于最大最小值都要查詢，而return隻能傳回一個，是以用ma和mi記錄最小值
LL query(int rt, int l, int r, int x, int y, LL &ma, LL &mi)
{
    if(x<=l && y>=r)
    {
        ma = max(ma,st_max[rt]);
        mi = min(mi,st_min[rt]);
        return ma - mi;
    }

    int mid = (l+r)>>1;
    if(y<=mid) query(rt*2,l,mid,x,y,ma,mi);
    else if(x>=mid+1) query(rt*2+1,mid+1,r,x,y,ma,mi);
    else query(rt*2,l,mid,x,mid,ma,mi),query(rt*2+1,mid+1,r,mid+1,y,ma,mi);

    return ma - mi;
}

int test(int len, int n, int k)
{
    for(int i = len-1; i<n; i++)
    {
        LL ma = -LNF, mi = LNF;
        if(query(1,0,n-1, i-len+1, i, ma,mi)<=1LL*k)
            return 1;
    }
    return 0;
}

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)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%lld", &a[i]);

        build(1,0,n-1);

        int l = 1, r = n;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(test(mid, n,k))
                l = mid+1;
            else
                r = mid-1;
        }
        printf("%d\n", r);
    }
    return 0;
}