HDU 5289 Assignment （二分+区间最值）

【题目链接】click here~~

【题目大意】：

给出一个数列，问当中存在多少连续子序列，子序列的最大值-最小值<k

【思路】：枚举数列左端点。然后二分枚举右端点，用ST算法求区间最值。（或用单调队列的思路）

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

typedef long long LL;

#define Max(a,b) a>b?a:b

#define Min(a,b) a>b?

b:a

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

int arr[N];

int n,k,m,tmp;

int dp_max[N][20],dp_min[N][20];

void rmq_init(){

    for(int i=1; i<=n; ++i) dp_max[i][0]=dp_min[i][0]=arr[i];

    double limit=log(n)/log(2.0);  // 换底公式

    for(int j=1; j<=(int)limit; ++j){

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

            dp_max[i][j]=Max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);

            dp_min[i][j]=Min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);

        }

    }

}

int rmq_max(int L,int R){   // 查询[L,R]之间的最大值

    int k=floor(log2((double)(R-L+1)));

    return Max(dp_max[L][k], dp_max[R - (1<<k) + 1][k]);

}

int rmq_min(int L, int R){   // 查询[L,R]之间的最小值

    int k=floor(log2((double)(R-L+1)));

    return Min(dp_min[L][k], dp_min[R - (1<<k) + 1][k]);

}

int solve(int L,int R){

    int k=floor(log2((double)(R-L+1)));

    int maxx=Max(dp_max[L][k],dp_max[R - (1<<k) + 1][k]);

    int minn=Min(dp_min[L][k],dp_min[R - (1<<k) + 1][k]);

    return maxx-minn;

}

inline LL read(){

    int c=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    return c*f;

}

int main(){

    int t;t=read();

    while(t--){

        n=read();k=read();

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

            arr[i]=read();

        }

        rmq_init();

        LL ans=0;

        for(int i=1; i<=n; ++i){//枚举左端点，二分右端点,ST求最值

            int ll=i,rr=n;

            while(ll<=rr){

                int mid=(ll+rr)>>1;

                if(solve(i,mid)>=k) rr=mid-1;

                else ll=mid+1;

            }

            if(solve(i,rr)<k)ans+=(rr-i+1);

            else ans+=(ll-i+1);

        }

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

    } return 0;

}

单调队列：

【思路】：

O(n)复杂度

用两个单调队列维护最大值，最小值，相当于双指针，初始，第一个第二个指针指向第一个数据，第一个指针按顺序不断向队尾加入数据，当最大值最小值的差大于等于k后，意味着新加入的这个不能作用于当前第二个指针的位置，也就能计算出，以第二个指针位置開始的连续子序列的个数。最后统计就能够了。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

typedef long long LL;

#define Max(a,b) a>b?a:b

#define Min(a,b) a>b?b:a

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

int arr[N];

int i,j,n,k,m,tmp;

deque <int >deq_max,deq_min;// maxvalue minvalue

inline LL read(){

    int c=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}

    return c*f;

}

int main(){

    int t;t=read();

    while(t--){

        n=read();k=read();

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

            arr[i]=read();

        }

        LL ans=0;

        while(!deq_max.empty()) deq_max.pop_back();

        while(!deq_min.empty()) deq_min.pop_back();

        for(i=0,j=0; i<n; ++i){

            while(!deq_max.empty()&&deq_max.back()<arr[i]) deq_max.pop_back();deq_max.push_back(arr[i]);

            while(!deq_min.empty()&&deq_min.back()>arr[i]) deq_min.pop_back();deq_min.push_back(arr[i]);

            while(!deq_max.empty()&&!deq_min.empty()&&deq_max.front()-deq_min.front()>=k){

                ans+=(i-j);

                if(deq_max.front()==arr[j]) deq_max.pop_front();

                if(deq_min.front()==arr[j]) deq_min.pop_front();

                j++;

            }

        }

        while(j<n){

            ans+=(i-j);

            j++;

        }

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

    } return 0;

}