题意：给出一个数列。问当中存在多少连续子区间，当中子区间的(最大值-最小值)<k

思路：设dp[i]为从区间1到i满足题意条件的解。终于解即为dp[n]。

此外 如果对于arr[i] 往左遍历 一直到arr[r] 此时从区间r到区间i满足(最大值-最小值)<k，再往左一位即越界 或者 不满足条件，此时有 dp[i]
= dp[i-1]
+ i - r
+ 1;

由于数据量大 往左遍历时 可能会超时 ，所以用rmq打表 查找r时用二分 就过了

代码：

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <cstdio>

#include <string>

#include <bitset>

#include <vector>

#include <queue>

#include <stack>

#include <cmath>

#include <list>

#include <map>

#include <set>

#define sss(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define mem1(a) memset(a,-1,sizeof(a))

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

#define ss(a,b) scanf("%d%d",&a,&b)

#define s(a) scanf("%d",&a)

#define INF 0x3f3f3f3f

#define w(a) while(a)

#define PI acos(-1.0)

#define LL long long

#define eps 10E-9

#define N 100010

using namespace std;

void mys(int& res) {

    int flag=0;

    char ch;

    while(!(((ch=getchar())>='0'&&ch<='9')||ch=='-'))

        if(ch==EOF)  res=INF;

    if(ch=='-')  flag=1;

    else if(ch>='0'&&ch<='9')  res=ch-'0';

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

    res=flag?-res:res;

}

void myp(int a) {

    if(a>9)

       myp(a/10);

    putchar(a%10+'0');

}

/********************the end of template********************/

int arr[N];

int sm[N][30], bg[N][30];

LL dp[N];

void rmq_init(int n) {

    for(int i = 0; i < n + 1; i++)   bg[i][0] = sm[i][0] = arr[i];

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

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

            bg[i][j] = max(bg[i][j - 1], bg[i + (1 << (j - 1))][j - 1]);

            sm[i][j] = min(sm[i][j - 1], sm[i + (1 << (j - 1))][j - 1]);

        }

    }

}

int rmq_min(int left, int right){

    int kk = 0;

    w((1 << (kk+1)) <= right - left +1) kk++;

    return min(sm[left][kk], sm[right - (1<<kk) +1][kk]);

}

int rmq_max(int left, int right){

    int kk = 0;

    w((1 << (kk+1)) <= right - left +1) kk++;

    return max(bg[left][kk], bg[right - (1<<kk) +1][kk]);

}

int getR(int L, int k, int R) {

    int l = L, r = R, m, ans;

    while(l <= r) {

        m = (l + r) >> 1;

        int view = rmq_max(m, R) - rmq_min(m, R);

        if(view < k) {

            ans = m;

            r = m - 1;

        }

         else l = m + 1;

    }

    return ans;

}

int main(){

    int t;

    s(t);

    w(t--){

        int n, k;

        mem(dp);

        ss(n, k);

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

            s(arr[i]);

        }

        rmq_init(n);

        dp[1] = 1;

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

            int R = getR(1, k, i);

            dp[i] = dp[i-1] + i - R + 1;

        }

        cout<<dp[n]<<endl;

    }

    return 0;

}