HDU 5289 Assignment（多校2015 RMQ 单调（双端）队列）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5289

2
4 2
3 1 2 4
10 5
0 3 4 5 2 1 6 7 8 9

5
28
Hint
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3] 
 

题意：
给出一个整数序列，求有多少个区间满足区间里的最大元素与最小元素的差不超过k”。

PS:

1：能够先用Rmq处理出区间的最值，再枚举区间。当然一味的枚举肯定没有以下两种方法快！

2：用单调（双端）队列维护区间最值

3：枚举左端点，二分右端点，用ST算法求区间最值

代码一例如以下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int MAXN = 100117;

int num[MAXN];

int F_Min[MAXN][30],F_Max[MAXN][30];

void Init(int n)
{
    for(int i = 1; i <= n; i++)
    {
        F_Min[i][0] = F_Max[i][0] = num[i];
    }

    for(int i = 1; (1<<i) <= n; i++)  //按区间长度递增顺序递推
    {
        for(int j = 1; j+(1<<i)-1 <= n; j++)  //区间起点
        {
            F_Max[j][i] = max(F_Max[j][i-1],F_Max[j+(1<<(i-1))][i-1]);
            F_Min[j][i] = min(F_Min[j][i-1],F_Min[j+(1<<(i-1))][i-1]);
        }
    }
}

int Query_max(int l,int r)
{
    int k = (int)(log(double(r-l+1))/log((double)2));
    return max(F_Max[l][k], F_Max[r-(1<<k)+1][k]);
}

int Query_min(int l,int r)
{
    int k = (int)(log(double(r-l+1))/log((double)2));
    return min(F_Min[l][k], F_Min[r-(1<<k)+1][k]);
}
int solve(int l, int r)
{
    return Query_max(l,r)-Query_min(l,r);
}
int main()
{
    int t;
    int n, k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&num[i]);
        }
        Init(n);
        __int64 ans = 0;
        int pos = 1;
        for(int i = 1; i <= n; i++)
        {
            while(solve(pos, i) >= k && pos < i)
            {
                pos++;
            }
            ans+=i-pos+1;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std ;
#define LL __int64
deque <LL> deq1 , deq2 ;
//单调队列，deq1最大值，deq2最小值
LL a[100010] ;
int main()
{
    int t , n , i , j ;
    LL k , ans ;
    scanf("%d", &t) ;
    while( t-- )
    {
        scanf("%d %I64d", &n, &k) ;
        for(i = 0 ; i < n ; i++)
            scanf("%I64d", &a[i]) ;
        if(k == 0)
        {
            printf("0\n") ;
            continue ;
        }
        while( !deq1.empty() ) deq1.pop_back() ;
        while( !deq2.empty() ) deq2.pop_back() ;
        for(i = 0 , j = 0 , ans = 0; i < n ; i++)  //i在前，j在后
        {
            while( !deq1.empty() && deq1.back() < a[i] ) deq1.pop_back() ;
            deq1.push_back(a[i]) ;
            while( !deq2.empty() && deq2.back() > a[i] ) deq2.pop_back() ;
            deq2.push_back(a[i]) ;
            while( !deq1.empty() && !deq2.empty() && deq1.front() - deq2.front() >= k )
            {
                ans += (i-j) ;
                //printf("%d %d,%I64d %I64d\n", i , j, deq1.front() , deq2.front() ) ;
                if( deq1.front() == a[j] ) deq1.pop_front() ;
                if( deq2.front() == a[j] ) deq2.pop_front() ;
                j++ ;
            }
        }
        while( j < n )
        {
            ans += (i-j) ;
            j++ ;
        }
        printf("%I64d\n", ans) ;
    }
    return 0 ;
}

#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long
#define Max(a,b) ((a)>(b)?
(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int N=200007;
int minn[N][20];//2^18=262144   2^20=1048576
int maxx[N][20];

//----------------------查询O(1)-------------
int queryMin(int l,int r)
{
    int k=floor(log2((double)(r-l+1)));//2^k <= (r - l + 1),floor()向下取整函数
    return Min(minn[l][k],minn[r-(1<<k)+1][k]);
}

int queryMax(int l,int r)
{
    int k=floor(log2((double)(r-l+1)));
    return Max(maxx[l][k],maxx[r-(1<<k)+1][k]);
}
//-------------------------------------------------

int calc(int l,int r)
{
    int k=log2((double)(r-l+1));
    int MAX=Max(maxx[l][k],maxx[r-(1<<k)+1][k]);
    int MIN=Min(minn[l][k],minn[r-(1<<k)+1][k]);
    return MAX-MIN;
}

int main()
{
    int T;
    int n,k,i,j,p;
    LL ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(i=1; i<=n; ++i)
        {
            scanf("%d",&j);
            minn[i][0]=maxx[i][0]=j;
        }
//------------------------------------------预处理O(nlogn)---------------
        for(j=1; (1<<j)<=n; ++j)//1<<j==2^j,枚举区间长度1，2，4，8。16。，。。，
            for(i=1; i+(1<<j)-1<=n; ++i)//i+(1<<j)-1表示区间右边界，枚举区间左边界
            {
                p=(1<<(j-1));
                minn[i][j]=Min(minn[i][j-1],minn[i+p][j-1]);
                maxx[i][j]=Max(maxx[i][j-1],maxx[i+p][j-1]);
            }
//-----------------------------------------------------------------------

//---------------------------枚举左端点，二分右端点---------------------------

        int l,r,mid;
        ans=0;
//左端点固定为i，右端点用l,r,mid去确定，最后用l和r中的当中一个，此时l+1==r
        for(i=1; i<=n; ++i)
        {
            l=i,r=n;
            while(l+1<r)
            {
                mid=(l+r)>>1;//(l+r)/2==(l+r)>>1
                if(calc(i,mid)<k)
                {
                    l=mid;
                }
                else
                {
                    r=mid-1;//自己去演示算法流程就知道r能够赋值mid-1
                }
            }
            if(calc(i,r)<k)
            {
                ans=ans+(LL)(r-i+1);
            }
            else
            {
                ans=ans+(LL)(l-i+1);
            }
        }
//---------------------------------------------------------------------------
        printf("%lld\n",ans);
    }
    return 0;
}