链接：https://ac.nowcoder.com/acm/contest/11256/K
来源：牛客网

题目描述

Given nn integers a1,a2,⋯ ,ana1,a2,⋯,an and mm queries. For each query, you are given a const kk and you should determine how many different pairs (l,r)(l,r) are there meeting the condition that the range of the subsequence al,al+1,⋯ ,aral,al+1,⋯,ar is strictly greater than kk.

Note: the range of a sequence equals the difference between the maximum and the minimum of the sequence.

输入描述:

The first line contains two integers n,m (1≤n≤105,1≤m≤100)n,m(1≤n≤105,1≤m≤100), denoting the number of given integers and the number of queries respectively.

The second line contains n integers a1,a2,⋯ ,an (1≤ai≤109)a1,a2,⋯,an(1≤ai≤109), denoting the given integers.

Next m lines each contains one integer k (1≤k≤109)k(1≤k≤109), denoting the queries.

输出描述:

Print mm lines each contains one integer, denoting the answers.

示例1

输入

复制

5 1
1 2 3 4 5
2

输出

复制

3

说明

There are three pairs, (1,4),(1,5),(2,5)(1,4),(1,5),(2,5), which meet the condition.

这个题帮我复习了好久都没写过的单调队列T*T

题意就是给一个序列，处理m次询问，每次询问输出有多少个连续子区间满足区间的极值（最大值-最小值）大于k。

首先注意到，只要一个区间的最大值和最小值的差大于k，那么这个区间是可以继续扩展的（此时最大值减最小值得到的差是单调不减的）。因此考虑枚举区间右端点r，先把右端点定下，然后看左端点可以取哪些位置。朴素的思路是从1到r - 1枚举左端点，但这样会有很大的问题：遍历+查询区间最值的总的\(O(n^2mlogn)\)复杂度肯定会T的妈妈都不认识（当然优化过以后貌似也可以用RMQ来做）。于是就想到了常见的维护最值的单调队列算法。

整体的思路就是：遍历区间右端点r，遍历的同时维护两个单调队列mx和mn用来存储数组元素对应的下标，其中mx用来访问最大值，mn用来访问最小值（这里的最大值是指取出mx的队头元素，这个位置对应的数是队列存储的所有位置对应的数中最大的）。通过这两个队列，我们可以以均摊为\(O(1)\)的时间复杂度找到离r最近的满足题目要求的左端点l。为什么要离r尽可能近呢？因为这样才可以直接计算r的贡献，避免重复计算区间造成答案变大的问题。由前面的结论，实际上\([1,l]\)都可以作为左端点，因此这个右端点对于答案的贡献就是\(l\)。

那么问题来了，怎么找左端点呢？返回去看一下mx和mn存储的都是什么：mx存储的是一系列下标，从队头到队尾下标对应的数组中的值是单调递减的，队头对应的数为最大值；mn同理，不过存储的值是单调递增的，队头对应的数为最小值。同时，由于是r边往右遍历边维护队列，因此mx和mx中实际存放的下标从队头到队尾也都是单调递增的！这样就好办了，右端点新遍历到一个位置时先维护队列，以mx为例，先把小于等于a[r]的元素弹出，因为这些元素对应的数不仅比a[r]小，位置还离r更远（不要忘记最终要使选出来的左端点尽可能靠右，而选出来的左端点就出现在这两个队列中），一定更劣。更新完了以后就是找左端点了，在满足条件的情况下不断将两个队列的队首弹出来并取较小值更新答案（较小的那个值是短板），最终就能得到尽可能靠近r的满足条件的最大的l了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
long long a[100005], k;
signed main() {
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)scanf("%lld",&a[i]);
    for(int i = 1; i <= m; i++) {
        cin >> k;
        long long ans = 0;
        deque<int> mx, mn;
        int l = 0;//注意这个l不能放在内循环里
        //此时的单调队列里不仅这些位置对应的数是单调递增/减的，这些位置也是单调递增的
        for(int r = 1; r <= n; r++) {
            while(mx.size() && a[r] >= a[mx.back()]) mx.pop_back();//因为要找的左端点必须尽可能靠右，比当前位置的数小同时位置更靠前的队列中的元素直接删除
            mx.push_back(r);
            while(mn.size() && a[r] <= a[mn.back()]) mn.pop_back();
            mn.push_back(r);
            while(mx.size() && mn.size() && a[mx.front()] - a[mn.front()] > k) {
                if(mx.front() < mn.front()) l = mx.front(), mx.pop_front();//取较小的更新l
                else l = mn.front(), mn.pop_front();
            }
            ans += 1ll * l;
        }
        cout << ans << endl;
    }

    return 0;
}