1.区间是一段的，不是断开的哟
2.代码是看着标程写的
3.枚举左端点，二分右端点流程：
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
#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;
}