【单调队列】2021牛客暑期多校训练营5 K King of Range

题目解析

给定数列，求有多少个子区间最大值减最小值 $<=k$；
单调队列维护区间最大值和最小值，维护双指针即可；

代码实现

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <unordered_map>
#include <deque>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 200000
#define mod 1000000007
#define MS 100009

LL n,m,k;
deque<LL > mx,mn;
LL a[MS];

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	while (m--){
		cin >> k;
		LL ans = (n+1)*n/2;
		int l = 1;
		while (!mx.empty()) mx.pop_back();
		while (!mn.empty()) mn.pop_back();
		
		for (int i=1;i<=n;i++){
			while (!mx.empty() && a[ mx.back() ] < a[i]) mx.pop_back();
			while (!mn.empty() && a[ mn.back() ] > a[i]) mn.pop_back();
			mx.push_back(i);
			mn.push_back(i);
			while (a[mx.front()] - a[mn.front()] > k){
				l++;
				while (mx.front() < l) mx.pop_front();
				while (mn.front() < l) mn.pop_front();
			}
			ans -= (i-l+1);
 	    }
		cout << ans << "\n";

	}
		
	return 0;	
}