单调栈学习笔记

单调栈基础

单调栈根据所维护的单调性可以分为四种：

• 严格递增栈。必须出栈至栈空或栈顶小于当前元素后，才入栈当前元素。
• 严格递减栈。必须出栈至栈空或栈顶大于当前元素后，才入栈当前元素。
• 非严格递增栈。必须出栈至栈空或栈顶小于等于当前元素后，才入栈当前元素。
• 非严格递减栈。必必须出栈至栈空或栈顶大于等于当前元素后，才入栈当前元素。

我在选择什么栈，选择栈后弹栈不等号方向怎么写，每次都得绕一会才能想明白，给我自己做个笔记。

考虑你往严格递增的序列每两个相邻的数中间应该填什么不等号？对了，小于号。

严格递增栈的意思其实就是一个从 栈底 到 栈顶 的严格递增序列，所以栈底对应序列的开头，栈顶对应序列的末尾。对于其它类型的栈也是如此，单调性指的都是栈底到栈顶这个方向。

换句话说，如果你的思维惯性地认为序列的开头在左侧，序列的结尾在右侧，那应该认为栈应该是向右开口的，在右面进出数，对应栈顶弹出和射入，序列尾部加数删数。

现在回来看：

严格递增栈。必须出栈至栈空或栈顶小于当前元素后，才入栈当前元素。

可以翻译为：

严格递增序列。必须删除尾数，或尾数小于要新加的数后，才把新数加入到序列的尾部。

是不是就很明显了？

比较栈顶和要加入的数的过程，应该是比较到我们所维护的那个单调性满足为止才入栈。我们在比较的时候，推荐在不等号的左面放上尾数，不等号的右面放上想要新加的数。因为如果这个新加的数真的加进去了，尾数应该在新加的数的左面。这样以来，不等号的选取就可以根据：单调递增的序列应该在每两个相邻数之间填写什么符号？来直接移植，不用动脑。

举个例子吧。如果我们要写单调非严格递减栈，分三步：

• 考虑单调非严格递减序列，每两个数之间应该填写大于等于号。
• 所以，将尾数写在左面，新加的数写在右面，中间的符号也应该是大于等于号。
• 这就是加栈的条件了：栈为空，或栈顶大于等于新加数。
• 那么弹栈的条件就是它的取反条件，直接套个 ! 即可。
• while(!(!st.empty() || st.top() >= a[i])) st.pop();
• 当然熟练了就会觉得上面这个写法很蠢了，直接将这个条件写成取反形式，如下：
• while(st.empty() && st.top() < a[i]) st.pop();
• 这个小于号也可以理解成：小于号会破坏我们要求的大于等于。

总之，将栈顶放在左侧，新加的数放在右侧，之间的不等号就能直接从对应单调序列中相邻元素之间的不等号来直接判断，就再也不用绕了。

单调栈基本性质

一些基本性质：

• 维护单调性的方式是：无论破坏多少个栈内的，也要让新元素进来。
• 如果是正着扫序列，则越靠近栈顶的元素，下标越大，距离当前指针越近。

接下来来看单调栈的两个实例。

NGE

当用到单调栈的时候，95% 都是在解决这个问题。

给定一个数组 \(a\)，对每个 \(i\)，求出 \(i\) 的下一个最近的比 \(a_i\) 大的数的下标 \(f(i)\)，如果不存在则 \(-1\)。

这个问题被称为 Next Greater Element 问题，即 NGE 问题。

上面这个问题要求解的是下一个比 \(a_i\) 大的数，也就是最小的 \(j >i\) 满足 \(a_j > a_i\)。我们换个写法，\(a_i <a_j\)，原因是我们期望把在序列左边的元素放在不等号的左边。然后，我们挑选与这个不等号 相反的 不等号，对应的单调栈。比如这里相反的不等号是 \(\ge\)（注意这里原来不取等的现在取等，原来取等的现在不取等），相邻两个元素之间是这个不等号的应该是非严格递减序列，所以我们应该选择非严格递减栈。

于是，从左到右扫，每个数都会被入栈一次。如果 \(a_i\) 是 \(a_j\) 进栈时被弹出的，那么 \(f(i) = j\)。如果 \(a_i\) 没被弹出过，\(f(i) = -1\)。

每个时刻单调栈内元素的含义是：待确定 NGE 的元素。这个思想尤为重要，可以看做单调栈的第三条性质。

也即，在单调栈刚好射入 \(a_i\) 后，单调栈中的任一元素 \(a_j\)，目前还没有找到它的 NGE。也即，\(a_j\) 的 NGE 要么不存在，要么下标 \(>i\)，现在还没扫到呢。

而先前被插入，后来已不在单调栈内的元素 \(a_{j'}\)，一定有 \(a_{j'}\) 的 NGE 存在，为 \(a_k\)，并且下标 \(j' < k \le i\)。

同时，考虑任意时刻非严格单调递减栈任意两个相邻的元素 \(a_i\) 和 \(a_j\)。设 \(a_i\) 靠近栈底，\(a_j\) 靠近栈顶，明显有 \(i <j\)，\(a_i \ge a_j\)。

如果 \(i < j - 1\)，则 \(a_{j - 1}\) 不在栈里。由于 \(a_{j - 1}\) 上一秒刚进栈，下一秒就被 \(a_j\) 弹出了，所以 \(a_{j - 1} < a_j\)。

如果 \(i < j - 2\)，意味着 \(a_{j - 2}\) 也没在栈里，那它要么被 \(a_{j - 1}\) 弹出去，要么被 \(a_{j}\) 弹出去。所以有 \(a_{j - 2} < a_{j - 1}\) 或 \(a_{j - 2} < a_j\)。无论如何，因为 \(a_{j - 1} < a_j\)，都有 \(a_{j - 2} < a_j\)。

非常类似地，我们可以推出对于任意 \(i < k <j\)，\(a_k < a_j\)。

所以可以推出 \(a_i \ge a_j > a_k\)。

这意味着，非严格单调递减栈中相邻的两个元素，在原序列中间夹着的所有元素，都比这两个元素更小。称之为性质四。

另外，对于严格单调递减栈，上面那个结论是 \(a_i > a_j \ge a_k\)，证明思路类似。

递增就是上面两种情况不等号反过来啦（这里不取等的接着不取等，取等的接着取等哦）。

这个结论可以推出：如果 \(i <k <j\)，有 \(a_i \ge a_k \ge a_j\)，并且 \(a_i\) 和 \(a_j\) 都在栈里，则这两个元素在单调栈中间一定还有元素（不一定是 \(a_k\)，但一定有元素）。

区间端点最大 / 小问题

P1823 COI2007 Patrik 音乐会的等待。

题意：统计数对 \((i, j)\) 的数量，满足 \(\max(a[i + 1 \ldots j - 1]) \le \min(a_i, a_j)\)。

让 \(j\) 从 \(1 \to n\)，统计有多少个 \(i\) 满足 \((i, j)\) 满足要求。考虑维护单调非严格递减栈。

在射入 \(a_j\) 之前，不在单调栈内的元素 \(a_i\)，要么还没进过栈（\(i \ge j\)），要么已经找到了 NGE（即存在一个 \(k\) 满足 \(i < k< j\) 且 \(a_k > a_i\)）。很明显，这两种情况对应的 \((i, j)\) 都是不满足要求的，所以我们只需要在单调栈中找满足条件的 \(a_i\) 即可。

那么满足条件的 \(a_i\) 又有哪些呢？

我们尝试将 \(a_j\) 射入，这样弹出若干次栈顶。设其中任一元素为 \(a_k\)，则 \(a_k\) 的 NGE 为 \(a_j\)。也即，\(a_k\) 下一个比它大的数就是 \(a_j\)，所以 \(\max(a[k + 1\ldots j - 1]) \le a_k < a_j\)，很明显，\((k, j)\) 是满足要求的。

一直弹到不弹为止，很明显，如果此时栈已经为空，那么上面的所有 \((k, j)\) 已经是所有右端点为 \(j\) 的满足条件的数对了（因为不在栈里的一定不是）。

如果栈不为空，设栈顶为 \(a_p\)。则 \(a_p \ge a_j\)。此时如果我们射入 \(a_j\)，那么 \(a_p\) 和 \(a_j\) 就已经相邻了，之前推得的 性质四 说明，\((p, j)\) 也是满足条件的。

那么比 \(a_p\) 还靠近栈底的元素是否满足条件？

分类讨论。

【第一种情况：\(\boldsymbol{a_p = a_j}\)】

考虑栈中等于 \(a_p\) 的其它元素 \(a_q\)。很明显所有满足条件的 \(a_q\) 都聚集在栈的顶部（我们先不急着射 \(a_j\)）。

根据性质四，在原序列中，所有满足条件的 \(a_q\) 之间，\(a_q\) 与 \(a_p\) 之间，\(a_p\) 与 \(a_j\) 之间的元素都 \(< a_p = a_q = a_j\)，所以所有的 \((q, j)\) 也是满足条件的。

考虑比 \(a_q\) 还大，又最靠近栈顶的元素 \(a_r\)。不难发现 \(a_r >a_q\)，而且 \(a_r\) 再往栈顶走一个元素就是 \(a_q\)。考虑 \(a_r\) 和这个 \(a_q\) 之间的元素，同样满足都小于 \(a_q\)。所以 \((r, j)\) 也满足条件。

但是，\(a_r\) 再往栈底走一个元素 \(a_s\)，即使 \(a_r = a_s\)，序列上 \(s\) 到 \(j\) 也会经过 \(a_r > a_j\)，因此 \((s, j)\) 已经不再合法。比 \(a_s\) 更靠近栈底的元素也会经过 \(a_r\)，同理不合法。

【第二种情况：\(\boldsymbol{a_p > a_j}\)】

此时，只有栈顶这个 \(a_p\) 是满足条件的：如果再射入 \(a_j\)，\(a_p\) 和 \(a_j\) 将相邻，中间的元素 \(< a_j < a_p\)，满足条件。

而不在栈顶的其它元素在序列上到 \(a_j\) 一定会经过 \(a_p > a_j\)，不合法，遗憾离场。

到这里本题正确性已经做完了，但事实上上面的 第一种情况，我们还要从栈顶一直往栈底扫，找极长的一个元素相同段，复杂度已经不对了。

怎么办呢？这里有一个小技巧，那就是把栈中相邻的两个相等的元素“打包”，记成一个 pair 元素，其中 pair 的第一项是元素本身，第二项是元素出现了多少次。这样我们只需要获取栈顶信息即可，复杂度正确。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2023-04-24 19:49:57 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2023-04-24 20:09:39
 */
#include <bits/stdc++.h>
#define int long long
inline int read() {
    int x = 0;
    bool f = true;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = false;
    for (; isdigit(ch); ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f ? x : (~(x - 1));
}
typedef std :: pair <int, int> pii;

signed main() {
    int n = read();
    std :: stack <pii> s;

    int ans = 0;
    while (n--) {
        int x = read();
        while (!s.empty() && s.top().first < x) {
            ans += s.top().second;
            s.pop();
        }
        if (s.empty())
            s.push({x, 1});
        else if (s.top().first == x) {
            int cnt = s.top().second;
            ans += cnt;
            s.pop();
            ans += (s.empty() ? 0 : 1);
            s.push({x, cnt + 1});
        } else {
            ++ans;
            s.push({x, 1});
        }
    }
    printf("%lld\n", ans);
    return 0;
}