ACM模版

描述

题解

第一次使用单调队列，也是第一次使用双向队列，看了前辈 光速小子 的博客后，算是搞懂了这道题。

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

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

大致就这样吧~~~没啥补充的了。

代码

#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 50005;

int N, K;
int A[MAXN];
ll ans = 0;
deque<int> dqMin, dqMax;

void solve()
{
    for (int i = 0, j = 0; i < N; i++)
    {
        while (j < N)
        {
            // 维护单调递增双向队列
            while (!dqMin.empty() && A[dqMin.back()] >= A[j])
            {
                dqMin.pop_back();
            }
            dqMin.push_back(j);

            // 维护单调递减双向队列
            while (!dqMax.empty() && A[dqMax.back()] <= A[j])
            {
                dqMax.pop_back();
            }
            dqMax.push_back(j);

            // dqMax 单调递减，dqMin 单调递增，所以只需要拿头比即可
            if (A[dqMax.front()] - A[dqMin.front()] <= K)
            {
                j++;
            }
            else
            {
                break;
            }
        }

        ans += (j - i);
        if (dqMin.front() == i)
        {
            dqMin.pop_front();
        }
        if (dqMax.front() == i)
        {
            dqMax.pop_front();
        }
    }
}

int main()
{
    scanf("%d%d", &N, &K);

    for (int i = 0; i < N; i++)
    {
        scanf("%d", A + i);
    }

    solve();

    printf("%lld", ans);

    return 0;
}