单调队列

Keep going ~

今天和Co老师学了单调队列

定义

单调队列，就是队列内元素单调的队列。

易错点

每次访问队列内元素时，都要保证队列非空，否则会 RE 。

做题步骤

去除队头不合法的元素
用当前元素，更新队列（从队尾
求当前位置的解

注：不一定按照 1 2 3 的顺序

例题

一

洛谷

给一个数列，和区间长度，要求输出，所有长度为的子串中的最小值和最大值。

思路：

枚举窗口的右端点（从数列第一个元素开始向后枚举），队头不合法即队头元素不在当前的窗口范围里；求最大值时，更新队列，就是把队尾中小于等于当前元素的都 pop 掉，求最小值时，时大于等于；当前位置的解，即为队头元素。

#include<deque>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 1000007
typedef long long ll;

inline ll rd() {
  ll x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

deque<int> Q;
ll a[N];
int fi[N], fa[N], n, k;

inline void work() {
    n = rd(), k = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    Q.clear();
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && Q.front() < i - k + 1) Q.pop_front();
        while (!Q.empty() && a[Q.back()] >= a[i]) Q.pop_back();
        Q.push_back(i);
        if (!Q.empty()) fi[i] = Q.front();
    }
    Q.clear();
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && Q.front() < i - k + 1) Q.pop_front();
        while (!Q.empty() && a[Q.back()] <= a[i]) Q.pop_back();
        Q.push_back(i);
        if (!Q.empty()) fa[i] = Q.front();
    }
    for (int i = k; i <= n; ++i) printf("%lld ", a[fi[i]]);
    puts("");
    for (int i = k; i <= n; ++i) printf("%lld ", a[fa[i]]);
}

int main() {
    work();
    return 0;
}

二

HDU

给一组数列，还有。求最长子串满足：

思路：

枚举区间右端点。两个队列分别用于计算区间最大值和最小值。做题步骤 2 即可进行；固定右端点的情况下，像右移动左端点，会使得变小；我们对的值进行讨论：

符合要求
不论怎么操作都得不到合法的解
向右移动左端点，直到

判断是否大于，如果大于就计算一次结果即区间长度，和原来的值取较大的；否则不计算，保留之前的答案。

下一个问题就是左端点：每次有元素弹出队列时，。

#include<deque>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 1000007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

deque<int> mn, mx;
int a[N];
int n, L, R;

inline void work() {
    for (int i = 1; i <= n; ++i) a[i] = rd();
    mn.clear(); mx.clear();
    int l = 1, ans = 0;
    for (int r = 1; r <= n; ++r) {
        while (!mn.empty() && a[mn.back()] > a[r]) mn.pop_back();
        while (!mx.empty() && a[mx.back()] < a[r]) mx.pop_back();
        mx.push_back(r); mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > R) {
            if (mx.front() < mn.front()) {
                l = mx.front() + 1; mx.pop_front();
            }else if (mx.front() > mn.front()) {
                l = mn.front() + 1; mn.pop_front();
            }else {
                l = mn.front() + 1; mn.pop_front(); mx.pop_front();
            }
        }
        if (a[mx.front()] - a[mn.front()] >= L) ans = max(ans, r - l + 1);
    }
    printf("%d\n", ans);
}

int main() {
    while (cin >> n >> L >> R) work();
    return 0;
}

三

HDU

给一个数，问最少通过几次变换可以把变成。

变换有以下两种：

if （如果是的倍数），。

变换 2 是 O(1) 的，但变换 1 是 O(t) 的。所以我们需要对变换 1 进行优化。

我们先写出动态转移的方程：

可以看出变换 1 的本质就是找出一个区间里的最小值，我们用单调队列进行优化。

注意：一定要在从队尾更新队列之前，保证当前位置的结果已经正确了。

#include<deque>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 1000007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

deque<int> q;
int f[N];

inline void work() {
    int x = rd(), k = rd(), t = rd();
    q.clear();
    f[1] = 0; q.push_back(1);
    for (int i = 2; i <= x; ++i) {
        f[i] = 1000007;
        if (i % k == 0) f[i] = min(f[i/k] + 1, f[i]);
        while (!q.empty() && q.front() < i - t) q.pop_front();
        if (!q.empty()) f[i] = min(f[q.front()] + 1, f[i]);
        while (!q.empty() && f[q.back()] >= f[i]) q.pop_back();
        q.push_back(i);
    }
    printf("%d\n", f[x]);
}

int main() {
    int t = rd();
    while (t--) work();
    return 0;
}