题意：求一段长度为n的序列里有多少个子区间内的最大值减最小值小于k。
解法：RMQ+尺取法或单调队列。RMQ可以用st或者线段树，尺取法以前貌似YY出来过……只是不知道是这个东西……
设两个标记l和r，对于区间[l, r]如果满足题中条件则ans+=(r - l + 1)，然后r右移一位，直到不符合条件，将l左移，直到符合条件。
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
int MIN[100005 << 2], MAX[100005 << 2];
int a[100005];
void pushupMIN(int rt)
{
MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);
}
void pushupMAX(int rt)
{
MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
if(l == r)
{
scanf("%d", &a[l]);
MIN[rt] = MAX[rt] = a[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushupMIN(rt);
pushupMAX(rt);
}
int getMIN(int ll, int rr, int l, int r, int rt)
{
if(ll <= l && rr >= r)
return MIN[rt];
int res = INT_MAX;
int m = (l + r) >> 1;
if(ll <= m) res = min(res, getMIN(ll, rr, lson));
if(rr > m) res = min(res, getMIN(ll, rr, rson));
return res;
}
int getMAX(int ll, int rr, int l, int r, int rt)
{
if(ll <= l && rr >= r)
return MAX[rt];
int res = 0;
int m = (l + r) >> 1;
if(ll <= m) res = max(res, getMAX(ll, rr, lson));
if(rr > m) res = max(res, getMAX(ll, rr, rson));
return res;
}
int main()
{
int T;
while(~scanf("%d", &T))
{
int n, k;
while(T--)
{
scanf("%d%d", &n, &k);
build(1, n, 1);
int flag = 0;
int l = 1, r = 0;
LL ans = 0;
while(r <= n)
{
if(r == n || flag)
{
l++;
int tmp1 = getMIN(l, r, 1, n, 1);
int tmp2 = getMAX(l, r, 1, n, 1);
if(tmp2 - tmp1 < k)
{
ans += r - l + 1;
flag = 0;
if(r == n)
break;
}
}
else
{
r++;
int tmp1 = getMIN(l, r, 1, n, 1);
int tmp2 = getMAX(l, r, 1, n, 1);
if(tmp2 - tmp1 < k)
{
ans += r - l + 1;
if(r == n)
break;
}
else
flag = 1;
}
}
printf("%lld
", ans);
}
}
return 0;
}