前言

考试就做起了这一道...还反反复复调了很久...

心情复杂/越来越感觉自己好弱

题目

difference.cpp   1S/128M
给出一个包括N个元素的整数数组A，包括A本身在内，共有 (N+1)*N / 2个非空子段。例如：1 3 2的子段为{1} {3} {2} {1 3} {3 2} {1 3 2}。
在这些子段中，如果最大值同最小值的差异不超过K，则认为这是一个合格的子段。给出数组A和K，求有多少符合条件的子段。
例如：3 5 7 6 3，K = 2，符合条件的子段包括：{3} {5} {7} {6} {3} {3 5} {5 7} {7 6} {5 7 6}，共9个。

Input
第1行：2个数N, K（1 <= N <= 50000, 0 <= K <= 10^9)
第2 - N + 1行：每行1个数，对应数组的元素Ai(0 <= Ai <= 10^9)

Output
输出符合条件的子段数量。

Sample Input
5 2
3
5
7
6
2

Sample Output
9

分析

这个问题的本质在于找到最大的区间[i, j]，保证从该区间的所有子区间都满足题意，但是如果每找到一个区间[i, j]就通通把它的子区间数加进去，那么一定会出现重复的情况，所以这里我们只要维护一边，然后去查找最大区间，最后再累加j - i + 1即可，代码中之所以直接累加j - i是因为此时的最大区间为[i, j - 1]

说到具体的实现所用的数据结构自然就是双端队列，维护一个记录最小值的单调递增队列和一个记录最大值的单调递减队列，最后只需要比较两个队列的头就可以保证[i, j]的合法性

记得删除队头：然后每次i结束前，将队列中位置<=i的删掉，因为对于i+1及后面的数而言，i不能对它们造成影响

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=50000,INF=0x3f3f3f3f;
ll a[MAXN+5],deq1[MAXN+5],deq2[MAXN+5];
int n,k;
ll Abs(ll a,ll b)
{
	if(a-b<0)
		return b-a;
	return a-b;
} 
void Solve()
{ 
	ll l1=1,l2=1,r1=0,r2=0,ans=0,j=1;
	for(int i=1;i<=n;i++)
	{
		//正常维护区间最值 	
		while(j<=n)
		{
			//Min 
			while(l1<=r1&&r1>0&&a[deq1[r1]]>=a[j])
				r1--;
			deq1[++r1]=j;
			//Max
			while(l2<=r2&&r2>0&&a[deq2[r2]]<=a[j])
				r2--;	
			deq2[++r2]=j;
			if(Abs(a[deq1[l1]],a[deq2[l2]])>k)
				break;
			j++;
		}
		ans+=j-i;
		while(l1<=r1&&deq1[l1]<=i)
			l1++;
		while(l2<=r2&&deq2[l2]<=i)
			l2++;
	} 
	printf("%lld\n",ans);
}
int main()
{
	//freopen("difference.in","r",stdin);
	//freopen("difference.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	Solve();
	return 0;
}