谁不喜欢香香软软的线段树呢？？？

康到题目，就知道难点就是求区间最大最小值了
谁叫我不会st表呢
可以用线段树来求解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+100;
ll n,m,a[N],tree1[4*N],tree2[4*N];//tree1，tree2分别表示最大最小值
void pushup(ll rt){
    tree1[rt]=max(tree1[rt<<1],tree1[rt<<1|1]);
    tree2[rt]=min(tree2[rt<<1],tree2[rt<<1|1]);
}
void build(ll rt,ll l,ll r){//建树
    if(l==r){
        tree1[rt]=tree2[rt]=a[l];
        return ;
    }ll mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
ll query1(ll rt,ll l,ll r,ll x,ll y){//查询区间最大
    if(x<=l&&r<=y){
        return tree1[rt];
    }ll mid=(l+r)>>1;
    ll mx=0;
    if(x<=mid)mx=max(mx,query1(rt<<1,l,mid,x,y));
    if(y>mid)mx=max(mx,query1(rt<<1|1,mid+1,r,x,y));
    return mx;
}
ll query2(ll rt,ll l,ll r,ll x,ll y){//同理，求最小
    if(x<=l&&r<=y){
        return tree2[rt];
    }
    ll mid=(l+r)>>1;
    ll mn=1e10;
    if(x<=mid)mn=min(mn,query2(rt<<1,l,mid,x,y));
    if(y>mid) mn=min(mn,query2(rt<<1|1,mid+1,r,x,y));
    return mn;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll l=i,r=n;
        while(l<r){//用二分不然会超时
            ll mid=(l+r+1)>>1;
            ll f1=query1(1,1,n,i,mid);
            ll f2=query2(1,1,n,i,mid);
            ll f3=f1-f2;
            if(f3<=m)l=mid;
            else r=mid-1;
        }ans+=l-i+1;
    }cout<<ans;
    return 0;
}

总时间nlognlogn