（2021牛客多校五）K-King of Range（单调队列/ST表）

样例输入：

5 1
1 2 3 4 5
2

 样例输出：

3

题意：给我们一个n，m代表一共有n个数，m组询问，接下来给定一个长度为n的数组，每组询问给我们一个k，问我们满足区间最大值-区间最小值>k的区间数目。

这道题目我给出两种思路：一种是用ST表+双指针来解决，另一种是用单调队列来解决

先来说一下ST表+双指针的做法：
由于这道题目并不涉及到元素修改，所以我们可以用ST表处理出来每个区间的最大值和最小值，这个是比较容易的，细节可以参考后面代码

我们枚举每个区间的左边界i看看以i作为区间左边界且满足题意的区间有多少个，容易发现其区间长度满足单调性，就是当区间[l,r]满足题意时，那么区间[l,r+1]也是符合题意的，因为区间[l,r+1]的最大值是不会比区间[l,r]的最大值小的，同理区间[l,r+1]的最小值也不会比区间[l,r]的最小值大的，所以明显区间[l,r+1]更优，所以当我们发现区间[l,r]满足题意时，对于任意的k大于r时那么区间[l,k]都是满足题意的，也就是说我们只需要用双指针找到第一个使得l作为区间左边界可以满足区间最值差大于k的右边界，那么我们就可以知道以l作为区间左边界的所有满足区间最值差大于k的区间个数，我们每次向右移动区间左指针进行遍历即可，这样双指针的复杂度是O（n）,所以总的复杂度就是ST表的复杂度，大概是20n

下面是代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+10;
int fx[N][21],fn[N][21];//记录最大值和最小值 
int Log[N];
int mx(int l,int r)
{
	int t=Log[r-l+1];
	return max(fx[l][t],fx[r+1-(1<<t)][t]);
}
int mn(int l,int r)
{
	int t=Log[r-l+1];
	return min(fn[l][t],fn[r+1-(1<<t)][t]);
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		Log[i]=log2(i);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&fx[i][0]);
		fn[i][0]=fx[i][0];
	}
	for(int i=1;i<=20;i++)
	for(int j=1;j+(1<<i)-1<=n;j++)
	{
		fx[j][i]=max(fx[j][i-1],fx[j+(1<<(i-1))][i-1]);
		fn[j][i]=min(fn[j][i-1],fn[j+(1<<(i-1))][i-1]);
	}
	while(m--)
	{
		int k;
		scanf("%d",&k);
		long long ans=0;
		int r=1;
		for(int l=1;l<=n;l++)
		{
			while(r<=n&&(mx(l,r)-mn(l,r)<=k)) r++;
			if(r>n) break;
			ans+=n-r+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

下面我来说一下单调队列的做法：

先来说一下单调队列的定义，这个看他的名字就知道了，就是元素具有单调性的一种队列，根据队列内元素单调递增还是单调递减又可分为单调递增序列和单调递减序列，其中：

单调递增序列队头元素一定是当前队列的最小值，用于维护一个区间的最小值

单调递减序列队头元素一定是当前队列的最大值，用于维护一个区间的最大值

知道了这些前备知识后我们来看下这道题该怎么做，我们用双指针来维护一下当前区间的边界，两个单调队列分别维护一下当前区间的最大值和最小值，然后我们每次向右移动一次右指针，并把当前右指针指向的元素加入队列中，然后判断以当前左指针和右指针指向的位置作为区间边界是否满足题意，如果满足题意，那么以当前左指针指向的位置作为区间左边界的合法区间数就有n-r+1个，因为当前右指针指向的位置一定是第一个满足题意的区间，否则左指针在上一次遍历时就已经向右移动，如果当前左右指针指向的位置作为区间边界是满足题意的，那么就向右移动左指针，记录其贡献，直到当前区间不满足最值大于k为止，再继续向右移动右指针，重复上述操作。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int q1[N],front1,tail1,q2[N],front2,tail2;
//q1[]维护一个单调递减队列，用于求区间最大值 
//q2[]维护一个单调递增队列，用于求区间最小值 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	while(m--)
	{
		int k;
		tail1=tail2=front1=front2=0;
		scanf("%d",&k);
		long long ans=0;
		for(int l=1,r=1;r<=n;r++)
		{
			while(front1<tail1&&a[q1[tail1-1]]<=a[r]) tail1--;
			while(front2<tail2&&a[q2[tail2-1]]>=a[r]) tail2--;
			q1[tail1++]=r;q2[tail2++]=r;
			while(a[q1[front1]]-a[q2[front2]]>k)
			{
				ans+=n-r+1,l++;
				if(q1[front1]<l) front1++;
				if(q2[front2]<l) front2++;
			}
		}
		printf("%lld\n",ans);
	}
	return 0; 
}