HDU 5289 Assignment(二分+RMQ)2015多校訓練一1002

右端点rが固定されていると仮定すると、最も遠く離れたlを見つけて、lからrまで要求を満たすことができれば、[l+1~r],[l+2~r].....すべて要求を満たす.だから右の端点を列挙して、最も遠い条件を満たす左の端点を探して、条件を満たすことができて、答えはこれらの長さを和します.
シーケンスは静的であるため,STアルゴリズムを用いてlog n時間に任意の区間における最大,最小値を求め,これらの値で最も遠いlを二分して解くことができる.
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
int N,k;
int a[100005];
int mx[100005][20];
int mi[100005][20];


void RMQ_init(){
    for(int i=0;i<N;i++){
        mx[i][0]=a[i];
        mi[i][0]=a[i];
    }
    for(int j=1;(1<<j)<=N;j++){
        for(int i=0;i+(1<<j)-1<N;i++){
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    }
}

int RMQx(int L,int R){
    int k=0;
    while((1<<(k+1)) <=R-L+1) k++;
    return max(mx[L][k],mx[R-(1<<k)+1][k]);
}

int RMQi(int L,int R){
    int k=0;
    while((1<<(k+1)) <=R-L+1) k++;
    return min(mi[L][k],mi[R-(1<<k)+1][k]);
}

int BS(int pos){
    int l=0,r=pos;
    int res=pos;
    while(r>=l){
        int mid=(l+r)/2;
        if(RMQx(mid,pos)-RMQi(mid,pos)<k){
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return res;
}


int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&k);
        for(int i=0;i<N;i++){
            scanf("%d",&a[i]);
        }
        RMQ_init();
        LL res=0;

        for(int i=0;i<N;i++){
            //cout<<px<<' '<<pi<<endl;
            int pos=BS(i);
            res+=(i-pos+1);
        }
        printf("%I64d
",res);
    }
    return 0;
}