51nod 1275 连续子段的差异（twopointer+单调队列）

　　对于每一个i找到最近的j满足最大值-最小值>K，对答案的贡献为j-i，用单调队列维护最值即可

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define ll long long 
using namespace std;
const int maxn=500010,inf=1e9;
int n,m,l,r,L,R,K;
int q[maxn],Q[maxn],a[maxn];
ll ans;
void read(int &k)
{
    int f=1;k=0;char c=getchar();
    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
    k*=f;
}
int main()
{
    read(n);read(K);
    for(int i=1;i<=n;i++)read(a[i]);
    l=1;r=0;L=1;R=0;
    for(int i=1,j=1;i<=n;i++)
    {
        while(j<=n)
        {
            while(l<=r&&a[q[r]]>=a[j])r--;
            while(L<=R&&a[Q[R]]<=a[j])R--;
            q[++r]=Q[++R]=j;
            if(a[Q[L]]-a[q[l]]>K)break;
            j++;
        }
        ans+=j-i;
        q[l]==i&&(l++);Q[L]==i&&(L++);
    }
    printf("%lld
",ans);
    return 0;
}