原题

King of Range

解析

m 的值不大, 每次时间在 n logn 以内即可

我们遍历整个数组, 以 i 为右边界, 检测是否有满足条件的左边界, 一次只加上左面的所有可能, 用两个双向队列维护两个单调栈, 一个存最大值, 一个存最小值, 这样可以帮助找到合适的左边界

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;
int n, m, k, q, l, ans;
int a[N];
void solve2()
{
	deque<int> qmi, qmx;
	l = 0, ans = 0;
	for(int i = 1; i <= n; i ++ )
	{
		while (!qmx.empty() && a[qmx.front()] - a[i] > k)
		{
			l = max(l, qmx.front());
			qmx.pop_front();
		}
		
		while (!qmi.empty() && a[i] - a[qmi.front()] > k)
		{
			l = max(l, qmi.front());
			qmi.pop_front();
		}
		
		ans += l;
		while (!qmx.empty() && a[qmx.back()] <= a[i])
		{
			qmx.pop_back();
		}
		qmx.push_back(i);
		while (!qmi.empty() && a[qmi.back()] >= a[i])
		{
			qmi.pop_back();
		}
		qmi.push_back(i);
	}
	cout << ans << "\n";
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = 1; i <= m; i ++ )
	{
		cin >> k;
		solve2();
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	while (T -- )
	{
		solve();
	}
}