hdu 5289(二分+RMQ) Assignment

题意：

给一个序列,然后求出连续的序列中最大和最小值之差小于k的个数。

思路

二分+ST
枚举每一个位置。二分下标,找一个最大的区间满足区间内最大最小值相差小于k,当前这个位置对于答案的贡献就是这个区间长度。
求一个静态数组的区间最大最小值,用ST算法就好了。

参考code:

/*
 #pragma warning (disable: 4786)
 #pragma comment (linker, "/STACK:0x800000")
 */
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }


#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define F(i, n) for(int (i)=0;(i)<(n);++(i))
#define rep(i, s, t) for(int (i)=(s);(i)<=(t);++(i))
#define urep(i, s, t) for(int (i)=(s);(i)>=(t);--(i))
#define repok(i, s, t, o) for(int (i)=(s);(i)<=(t) && (o);++(i))
#define MEM0(addr) memset((addr), 0, sizeof((addr)))
#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(pair, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define SZ(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define ll long long
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >
#define ls u << 1
#define rs u << 1 | 1
#define lson l, mid, u << 1
#define rson mid, r, u << 1 | 1
#define debug(x) cout << #x << " = " << x << endl

const int INF = 0x3f3f3f3f;
const double eps = 1e-9;
const int MAXN = 100010;
int dp1[MAXN][20];
int mm1[MAXN];
int dp[MAXN][20];
int mm[MAXN];
void initRMQ1(int n,int b[]) {
    mm1[0] = -1;
    for(int i = 1; i <= n; i++) {
        mm1[i] = ((i&(i-1)) == 0)?mm1[i-1]+1:mm1[i-1];
        dp1[i][0] = b[i];
    }
    for(int j = 1; j <= mm1[n]; j++)
        for(int i = 1; i + (1<<j) -1 <= n; i++)
            dp1[i][j] = max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
}
int rmq1(int x,int y) {
    int k = mm1[y-x+1];
    return max(dp1[x][k],dp1[y-(1<<k)+1][k]);
}

void initRMQ2(int n,int b[]) {
    mm[0] = -1;
    for(int i = 1; i <= n; i++) {
        mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
        dp[i][0] = b[i];
    }
    for(int j = 1; j <= mm[n]; j++)
        for(int i = 1; i + (1<<j) -1 <= n; i++)
            dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq2(int x,int y) {
    int k = mm[y-x+1];
    return min(dp[x][k],dp[y-(1<<k)+1][k]);
}

int n,k;
int a[MAXN];

int judge(int x,int y){
    if(rmq1(x,y) - rmq2(x,y) < k)
        return 1;
    return 0;
}

int main() {
    //READ("in.txt");
    int T;
    scanf("%d",&T);
    int l,r,m;
    ll ans;
    while(T--){
        scanf("%d%d",&n,&k);
        ans=0;
        rep(i,1,n) scanf("%d",&a[i]);
        initRMQ1(n,a);
        initRMQ2(n,a);
        rep(i,1,n){
            l = i,r = n;
            int e = i;
            while(l <= r){
                //cout << m << endl;
                m = (l+r) >> 1;
                if(judge(i,m)){
                    e = m;
                    l = m + 1;
                }else{
                    r = m - 1;
                }
            }
            //cout << ans << endl;
            ans += (e-i+1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}