单调队列学习笔记

简单的问题引入

例题:CH1201

输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。

以前写的题解:CH1201:最大子序和题解

首先思考暴力:枚举端点和不大于\(m\)的长度,前缀和搞一搞就好,时间复杂度为\(O(n^2)\),肯定超时。我们可以考虑优化这个算法。

单调队列

对于上面的问题,我们可以思考:我们肯定忽略了额外的信息,换句话说我们在运算过程中肯定忽略掉了一些可以进行优化的信息。考虑将可能的答案集设为\(S\)。我们只想要能使答案变大的决策,且这个决策点的距离不能超过\(m\),但我们又不想失去任何一个点作为答案的可能,怎么办?

我们可以对整个序列进行遍历。遍历过程中将可能有用的答案加入\(S\)中,将一定没用的答案直接剔除。首先,我们可以先确定哪些是一定没用的答案:

  • 距离超出\(m\)的。
  • 前缀和更大的(这样的话差就会变小,也就是区间和会变小)。

抽象点讲,假设已经遍历到位置\(i\),那么集合\(S\)内有决策点\(j\),如果满足两者之一,即为没用的答案

  • \(j-i+1>m\)
  • \(sum[i]>sum[j]\)

在单调队列中,我们只要可能有用的答案,我们一定会剔除掉没用的答案。所以,第一个条件我们可以通过队列的顺序保证,并且每次遍历时检查队头的情况;第二个条件我们可以考虑遍历时剔除掉队尾即可。为了让每个答案都不被预先抛弃,我们会将其放入入队列中。每个元素最多出入队各一次,时间复杂度为\(O(n)\)。

二维技巧

例题:P2216 [HAOI2007]理想的正方形

有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

首先考虑不优秀的暴力:枚举左上端点\((i,j)\),然后暴力计算\(n*n\)个点的极差,时间复杂度\(O(n^4)\)。

考虑优化:先从横行的角度进行处理,考虑维护每一行中的点作为右下端点,用两个单调队列处理出本行的最大最小值;之后从竖行的角度而言,求出一片区域(\(n^2\))的极差更新答案即可。

// P2216.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#define pr pair<int, int>
using namespace std;
const int MX_A = 1020, MX_N = 200;
int a, b, n, mat[MX_A][MX_A], maxrow[MX_A][MX_A], minrow[MX_A][MX_A], Ymx[MX_A][MX_A], Ymi[MX_A][MX_A];
int main()
{
    scanf("%d%d%d", &a, &b, &n);
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            scanf("%d", &mat[i][j]);
    deque<int> dqx, dqi;
    for (int i = 1; i <= a; i++)
    {
        dqx.clear(), dqi.clear();
        dqx.push_front(1), dqi.push_back(1);
        for (int j = 2; j <= b; j++)
        {
            while (!dqx.empty() && mat[i][j] >= mat[i][dqx.back()])
                dqx.pop_back();
            while (!dqi.empty() && mat[i][j] <= mat[i][dqi.back()])
                dqi.pop_back();
            dqx.push_back(j), dqi.push_back(j);
            while (!dqx.empty() && j - dqx.front() >= n)
                dqx.pop_front();
            while (!dqi.empty() && j - dqi.front() >= n)
                dqi.pop_front();
            if (j >= n)
                maxrow[i][j - n + 1] = mat[i][dqx.front()], minrow[i][j - n + 1] = mat[i][dqi.front()];
        }
    }
    for (int i = 1; i <= b - n + 1; i++)
    {
        dqx.clear(), dqi.clear();
        dqx.push_front(1), dqi.push_back(1);
        for (int j = 2; j <= a; j++)
        {
            while (!dqx.empty() && maxrow[j][i] >= maxrow[dqx.back()][i])
                dqx.pop_back();
            while (!dqi.empty() && minrow[j][i] <= minrow[dqi.back()][i])
                dqi.pop_back();
            dqx.push_back(j), dqi.push_back(j);
            while (!dqx.empty() && j - dqx.front() >= n)
                dqx.pop_front();
            while (!dqi.empty() && j - dqi.front() >= n)
                dqi.pop_front();
            if (j >= n)
                Ymx[j - n + 1][i] = maxrow[dqx.front()][i], Ymi[j - n + 1][i] = minrow[dqi.front()][i];
        }
    }
    int ans = 2e9;
    for (int i = 1; i <= a - n + 1; i++)
        for (int j = 1; j <= b - n + 1; j++)
            ans = min(ans, Ymx[i][j] - Ymi[i][j]);
    printf("%d", ans);
    return 0;
}

很多二维统计题都可以用这样的套路:点动成线,线动成面。

练习题

P2219 [HAOI2007]修筑绿化带

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注