单调栈学习笔记

发表于 2024-11-12 更新于 2025-03-28 分类于 Algorithm 阅读次数：本文字数： 20k

单调栈的本质是前缀的后缀最值，可以用来维护一些区间最值或一些连续单调的情况。单调栈上二分更是将单调栈的性质运用地淋漓尽致。

单调栈

单调栈，就是在栈的先进先出的基础上，要求栈里面的顺序从栈顶到栈底具有单调性。有了这样的数据结构，我们可以在\(O(n)\)时间内维护所有元素左边/右边的第一个比自己大/小的元素的位置。注意，本文的单调性都是从栈顶到栈底的顺序。

实现

左边第一个比自己大的元素位置——单调递增栈

我们维护栈的单调性，既然是递增的，那么栈顶的元素就应该比栈里的所有元素小，所以新入栈的元素应该是比栈顶小的元素，如果满足这样的条件，就说明栈顶就是第一个比当前位置大的元素。否则，我们直接弹出栈顶，栈顶的元素也不会再对后面的答案有贡献了。（因为后面新加进来的数会先比较当前的位置，而当前位置的元素是比栈顶大的），随后我们重复上面的步骤，直到栈为空或栈顶的元素比当前元素大。前一种情况说明左边已经不存在比自己大的元素了，我们特判处理掉，后一种情况就找到了第一个比自己大的元素位置。

在实现细节上，由于需要找到的是位置，因此我们存入栈里的应该是下标，可以通过下标定位元素的值，而存元素的值是无法\(O(1)\)找到下标的。

vector<int>stk;
for(int i = 0;i<n;i++){
  	while(!stk.empty() && a[i] >= a[stk.back()]){
      	stk.pop_back();
    }
  	if(stk.empty()){
				pos[i] = -1;
    }else{
      	pos[i] = stk.back();
    }
  	stk.push_back(i);
}

由于每个元素都会入栈一次，最多出栈一次，所以时间复杂度是\(O(n)\)

左边第一个比自己小的元素位置——单调递减栈

此时，我们希望从栈顶到栈底是递减的，这样就能找到比自己小的元素。

vector<int>stk;
for(int i = 0;i<n;i++){
  	while(!stk.empty() && a[i] <= a[stk.back()]){
      	stk.pop_back();
    }
  	if(stk.empty()){
				pos[i] = -1;
    }else{
      	pos[i] = stk.back();
    }
  	stk.push_back(i);
}

右边第一个比自己大的元素位置——单调递增栈

找右边的数其实和左边的数差距不大，但是注意遍历顺序：我们此时应该从右到左遍历。

vector<int>stk;
for(int i = n - 1;i>=0;i--){
  	while(!stk.empty() && a[i] >= a[stk.back()]){
      	stk.pop_back();
    }
  	if(stk.empty()){
      	pos[i] = -1;
    }else{
      	pos[i] = stk.back();
    }
  	stk.push_back(i);
}

但是，如果我们想要统一从左向右遍历，就会出现问题：由于入栈时尚不清楚右边的数的情况，所以无法确定右边的数第一个比自己小的元素位置。我们考虑维护一个单调递增栈，在出栈时维护位置：因为一个元素出栈时，说明当前遍历到的数比它大，就找到了这个位置。同时，在遍历完之后栈不为空，还有部分元素没有确定位置，此时我们将栈弹出，说明栈中的元素都没有在右边找到比自己大的元素，全部特判即可。还需要注意取等条件：此时相等的情况下不应该弹出栈，因为两个数的答案应该在是相同位置，在同一次操作出栈才对。

vector<int>stk;
for(int i = 0;i<n;i++){
		while(!stk.empty() && a[i] > a[stk.back()]){
      	pos[stk.back()] = i;
      	stk.pop_back();
    }
  	stk.push_back(i);
}
while(!stk.empty()){
  	pos[stk.back()] = -1;
  	stk.pop_back();
}

右边第一个比自己小的元素位置——单调递减栈

同理，我们维护单调递减栈。

vector<int>stk;
for(int i = n - 1;i>=0;i--){
  	while(!stk.empty() && a[i] <= a[stk.back()]){
      	stk.pop_back();
    }
  	if(stk.empty()){
      	pos[i] = -1;
    }else{
      	pos[i] = stk.back();
    }
  	stk.push_back(i);
}

vector<int>stk;
for(int i = 0;i<n;i++){
		while(!stk.empty() && a[i] < a[stk.back()]){
      	pos[stk.back()] = i;
      	stk.pop_back();
    }
  	stk.push_back(i);
}
while(!stk.empty()){
  	pos[stk.back()] = -1;
  	stk.pop_back();
}

总结

上边的分类解法有点绕口，可以简单记为以下条规则：

无论哪种题型，都建议从左到右遍历元素。
查找 「比当前元素大的元素」 就用 单调递增栈，查找 「比当前元素小的元素」 就用 单调递减栈。
从 「左侧」 查找就看 「插入栈」 时的栈顶元素，从 「右侧」 查找就看 「弹出栈」 时即将插入的元素（弹出栈不取等）。

应用

对于数组中的每个数\(a_i\)，寻找以\(a_i\)为最小值的最长区间的左右端点

之前的实现中，我们只能找到左右的第一个比自己小的数，那么在这两个端点之间，每一个元素都应该是比给定的元素大的，所以区间的左右端点最长可以拓展到这两个位置（开区间）,因此，我们可以在\(O(n)\)的时间里对于每个元素处理出左右端点。

vector<int> l(n + 1), r(n + 1);
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] <= a[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            l[i] = 1;
        } else {
            l[i] = stk.back() + 1;
        }
        stk.push_back(i);
    }
    stk.clear();
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] < a[stk.back()]) {
            r[stk.back()] = i - 1;
            stk.pop_back();
        }
        stk.push_back(i);
    }
    while (!stk.empty()) {
        r[stk.back()] = n;
        stk.pop_back();
    }

规律：大于等于——单调递增栈——以当前元素为最大值能拓展到的区间。

HDU 5696 区间的价值

给出一个长度为\(n\)的数组\(a_i\)，求数组内长度为\(1-n\)的区间内最大值和最小值的乘积最大值。

题解

我们可以用ST表来\(O(n\log n)\)预处理最大/小值，\(O(1)\)查找区间的最大值，如果枚举区间左右端点，时间复杂度是\(O(n^2)\)。

我们发现，主要消耗在寻找不可能有更优答案的区间了，考虑优化。事实上，每个数都可以作为某个区间的最小值，所以对于每个数，我们可以求出以它为最小值的区间最长能拓展到哪里。这样，我们对于每个数，都可以求出这一段区间的最小值和最大值的乘积（最大值用ST表维护，最小值就是\(a_i\)。考虑到随着区间长度的减少，答案一定不会减少（要么不变，要么最大值增加，要么最小值增加），因此我们从长度为\(n\)的区间开始，依次向下转移，过程中均取最大值。时间复杂度\(O(n\log n)\)

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct ST {
    const int n, k;
    vector<int> in1, in2;
    vector<vector<int>> Max, Min;
    ST(int n) : n(n), in1(n + 1), in2(n + 1), k(__lg(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
        Min.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in1[i];
            Min[0][i] = in2[i];
        }
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
                Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
    int getMin(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return min(Min[k][l], Min[k][r - (1 << k) + 1]);
    }
};

void solve(int n) {
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> l(n + 1), r(n + 1);
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] <= a[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            l[i] = 1;
        } else {
            l[i] = stk.back() + 1;
        }
        stk.push_back(i);
    }
    stk.clear();
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] < a[stk.back()]) {
            r[stk.back()] = i - 1;
            stk.pop_back();
        }
        stk.push_back(i);
    }
    while (!stk.empty()) {
        r[stk.back()] = n;
        stk.pop_back();
    }
    ST st(n);
    for (int i = 1; i <= n; i++) {
        st.in1[i] = a[i];
    }
    st.init();
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        int len = r[i] - l[i] + 1;
        dp[len] = max(dp[len], st.getMax(l[i], r[i]) * a[i]);
    }
    int mx = dp[n];
    for (int i = n - 1; i >= 1; i--) {
        dp[i] = max(mx, dp[i]);
        mx = dp[i];
    }
    for (int i = 1; i <= n; i++) {
        cout << dp[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 1;
    while (cin >> n) {
        solve(n);
    }
    return 0;
}

HDU1506 Largest Rectangle in a Histogram

给定一些矩形，假设宽度都是1，高度为\(a_i\)，求这些连续的矩形中最大包含的子矩形的面积。

题解

显然我们对每个元素维护以它为最小值的最长区间，然后扫描每个元素，答案就是高度乘宽度的最大值。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(int n) {
    if (!n) {
        return;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> l(n), r(n);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[i] <= a[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            l[i] = 0;
        } else {
            l[i] = stk.back() + 1;
        }
        stk.push_back(i);
    }
    stk.clear();
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[i] < a[stk.back()]) {
            r[stk.back()] = i - 1;
            stk.pop_back();
        }
        stk.push_back(i);
    }
    while (!stk.empty()) {
        r[stk.back()] = n - 1;
        stk.pop_back();
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, (r[i] - l[i] + 1) * a[i]);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while (cin >> n) {
        solve(n);
    }
    return 0;
}

P6503 [COCI2010-2011#3] DIFERENCIJA

给定一个长度为\(n\)的序列\(a_i\)，求： \[ \Sigma_{i=1}^{n}\Sigma_{j=i}^{n}(\max_{i\le k\le j}a_k - \min_{i\le k\le j}a_k) \]

题解

首先我们分开求每个区间的最大值和和最小值和。

对于求最大值和，考虑每一个数对于它的区间的贡献。设dp[i]表示以位置\(i\)结尾的区间产生的贡献，设lmax[i]表示位置\(i\)左边的第一个比它大的元素的位置，那么应该有dp[i] = dp[lmax[i]] + (i - lmax[i]) * a[i]，这是因为dp[lmax[i]]确定了区间长度超过i - lmax[i的区间前面的最大值之和，而长度小于等于i - lmax[i]的区间，a[lmax[i]]是贡献不到的，所以是由a[i]来贡献（因为根据lmax[i]的定义，这些区间的最大值都应该是a[i]。

这样，我们可以累积所有以\(i\)的区间的最大值答案，同理再减去最小值，就是最终答案了。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1), g(n + 1), lmin(n + 1), lmax(n + 1);
    int ans = 0;
    vector<int> stk;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] >= a[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            lmax[i] = 0;
        } else {
            lmax[i] = stk.back();
        }
        stk.push_back(i);
    }
    stk.clear();
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] <= a[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            lmin[i] = 0;
        } else {
            lmin[i] = stk.back();
        }
        stk.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        f[i] = f[lmax[i]] + (i - lmax[i]) * a[i];
        g[i] = g[lmin[i]] + (i - lmin[i]) * a[i];
        ans += f[i] - g[i];
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Codeforces Round 971 (Div. 4) G1，G2

题意

给定一个数组\(a_i\)和长度\(k\)，可以进行任意次数的操作：把一个位置的数变成另一个数。定义\(f(l,r)\)为把\(a_i\)到\(a_r\)的数变成长度至少为\(k\)的公差为1的等差数列所需要的最小操作次数。现在给定\(q\)次询问，每次询问给定\(l,r\)，求出\(\sum_{i=l+k-1}^{r}f(l,i)\)

G1: 满足\(r-l = k - 1\)（给定的区间长度恰好为\(k\)）

G2: 满足\(r - l \ge k - 1\)（给定的区间长度大于等于\(k\)）

题解

首先考虑G1，固定长度为\(k\)的区间我们想到了滑动窗口。想要一段序列为等差数列，不妨我们直接把所有数都减去下标，这样我们只需要让整个区间所有数都相同即可。我们统计区间内出现次数最多的数是多少，那么可以\(O(n)\)或\(O(n\log n)\)预处理，\(O(1)\)回答所有询问。

在G2中，我们的答案变成了长度大于等于\(k\)的前缀区间的和，注意到我们只需要让连续\(k\)个数变成等差数列即可，所以一个区间的\(f(l,r)\)应该是\(\min_{i=l}^{r-k+1}f(i,i+k-1)\)。那么对于一次询问，随着区间逐渐扩展，区间由短到长\(f\)一定是非递增的，我们记\(b_i\)为\(f(i,i+k-1)\)（即G1预处理的结果）因此我们可以预处理出每个位置右边第一个比它小的\(b_j\)，这一步可以通过单调栈完成。所以单次询问的答案可以拆分成区间内每一个数能够贡献的位置之和，即从左到右第一个数开始，单调栈中的数能够维护的区间乘上对应的数。

但是，即使这样做，考虑\(b_i\)连续递减的情况，对于一次询问，从左到右需要不停地跳转，时间复杂度还是不可接受，考虑优化。

考虑到右边的数能够贡献的区间只能在右边，而左边的数能够贡献的区间可能是全局，我们将询问离线处理：按照左端点从大到小排序，对于每个数都求出以它为最小值的区间。我们利用树状数组和差分记录下每个数的贡献，按照询问的顺序，我们从右到左遍历每个数直到它能贡献的区间不超出当前处理的区间左端点，用\(l[i]\)和\(r[i]\)分别记为位置\(i\)能够贡献到的区间左右端点（即以\(i\)为最小值的区间），那么遍历的过程中我们利用树状数组和差分修改对于区间的贡献，即区间和加上\((r[i] - i + 1) * b_i\)。除此之外，在这个数不能再贡献答案所在的区间时（即现在处理的区间左端点小于\(l[i]\)），还应该去除它对于答案的贡献。

具体为，考虑每个位置\(i\)只能贡献到\(r[i]\)，那么我们利用维护区间的数据结构给这段区间修改，如果是树状数组的话要小心\(r[i]\)可能不在我们要求的\([L,R]\)范围内，所以我们应该考虑到这种情况额外加上没有被算进去的贡献。

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Fenwick {
    int n;
    vector<int> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) {
        n = n_;
        a.assign(n, 0);
    }
    void add(int x, const int &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    int sum(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    int rangeSum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n), cnt(2 * n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] += n - i - 1;
    }
    vector<int> f(n - k + 1);
    vector<int> freq(n + 1);
    int res = 0;
    for (int i = 0; i < k - 1; i++) {
        freq[cnt[a[i]]]--;
        res = max(res, ++cnt[a[i]]);
        freq[cnt[a[i]]]++;
    }
    for (int i = 0; i <= n - k; i++) {
        freq[cnt[a[i + k - 1]]]--;
        res = max(res, ++cnt[a[i + k - 1]]);
        freq[cnt[a[i + k - 1]]]++;
        while (freq[res] == 0) {
            res--;
        }
        f[i] = k - res;
        freq[cnt[a[i]]]--;
        cnt[a[i]]--;
        freq[cnt[a[i]]]++;
    }
    const int N = f.size();
    vector<int> l(N), r(N, N);
    vector<int> stk;
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && f[i] <= f[stk.back()]) {
            r[stk.back()] = i;
            stk.pop_back();
        }
        if (!stk.empty()) {
            l[i] = stk.back() + 1;
        }
        stk.push_back(i);
    }
    vector<int> ans(q);
    vector<array<int, 3>> ask(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r = r - k + 1;
        ask.push_back({l, r, i});
    }
    sort(ask.begin(), ask.end(), greater());
    vector<array<int, 3>> e;
    for (int i = 0; i < N; i++) {
        e.push_back({i, i, 1});
        e.push_back({l[i] - 1, i, -1});
    }
    sort(e.begin(), e.end(), greater());
    Fenwick bit0(n + 1), bit1(n + 1);
    for (int j = 0; auto [L, R, i] : ask) {
        while (j < e.size() && e[j][0] >= L) {
            auto [_, k, coef] = e[j++];
            bit0.add(r[k], coef * f[k]);
            bit1.add(r[k], coef * r[k] * f[k]);
            bit0.add(k, -coef * f[k]);
            bit1.add(k, -coef * k * f[k]);
        }
        ans[i] += bit0.rangeSum(R, N + 1) * R;
        ans[i] += bit1.sum(R);
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

维护数列的前缀的后缀最值

我们按顺序把元素加入到单调栈时，其实栈里的元素就是前缀的后缀最值。假设我们需要找到前缀的后缀最大值，那么新加入单调递增栈中的数就是一个答案，同时考虑栈里的元素：如果栈里的元素大于新加入的数，它仍然可以作为后缀最大值，否则，栈里的元素不大于新元素了，它不能作为一个后缀的最大值。

求数列所有后缀最大值的位置

给出\(n\)个数依次加入数组中，按顺序输出每次给出一个数之后，当前数组所有后缀最大值的位置的异或和。（后缀最大值指的是对于一个位置，后面所有的数都小于它）。注意\(a_i < 2^{64}-1\)。

题解

本题揭示了单调栈的本质：维护前缀的后缀最值。因为后缀最大值要求在当前后缀中，其余的的数都小于它，显然从左到右遍历时，新加入的数就是一个后缀（大小为1），我们考虑之前的数的情况：如果前一个数也是后缀最大值，那么前一个数应该大于当前的数，否则就不是，此时它再也不可能是后面新加入的数的后缀最大值了，因为永远不会比当前的数大。因此，我们维护一个单调递增的栈，在加入元素过程中弹出元素并维护异或和。

注意：long long的范围是\(-2^{63} - 2^{63}-1\)，本题是\(2^{64}-1\)，应该用unsigned long long

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long

void solve() {
    int n;
    cin >> n;
    vector<int> a;
    a.reserve(n);
    vector<int> stk;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        while (!stk.empty() && a[i] >= a[stk.back()]) {
            ans ^= stk.back() + 1;
            stk.pop_back();
        }
        ans ^= (i + 1);
        cout << ans << "\n";
        stk.push_back(i);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

[COI2007] Patrik 音乐会的等待

一群人在排队，如果两个人可以相互看见，那么要么他们相邻，要么他们之间的人的身高都小于等于他们两人的身高，求能互相看见的人的对数。

题解

首先，计数时不能有重复的情况，因此我们只统计每个人向前看的对数，这样符合我们从左往右遍历的顺序。

先不考虑身高相同的情况，由于中间的人的身高只能比左右两个人矮，所以对于\(i\)位置，\(i\)能看到的人都是它入栈前的后缀最大值，这是因为我们维护一个单调递增栈，那么栈里的元素从栈顶到栈底都应该是递增的顺序，如果\(a_i > a[stack.top()]\)，说明\(i\)和栈顶之间的元素都是比他们小的，（否则会出现在栈里），所以统计的答案加一。

接下来是身高相同的情况，如果两个相邻的人的身高相同，那么排在后面的人看到的人数应该是前面的人看到的人数+1，这是因为后面的人能看到前面的人看到的所有人，还能看到前面的人，所以我们维护每个人看到的个数，\(O(n)\)即可解决。

其次，还需要特判一些情况，当一个数入栈前栈为空，说明它要么是第一个数，要么是最大的数，如果是前一种情况，是不能统计答案的，而对于后一种情况，它能看到的每一个人在被弹出栈的时候都已经被统计了，所以只要栈为空就不需要再次统计了。而如果栈不为空，这个人还能看到栈顶的一个人，答案还需要加一。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> stk, cnt(n, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[i] >= a[stk.back()]) {
            ans += cnt[stk.back()];
            if (a[i] == a[stk.back()]) {
                cnt[i] = cnt[stk.back()] + 1;
            }
            stk.pop_back();
        }
        if (!stk.empty()) {
            ans++;
        }
        stk.push_back(i);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时间复杂度：\(O(n)\)

Codeforces Beta Round 5 E - Bindian Signalizing

在上一题的基础上，本题把队列变成了环形队列，求能相互看到的人的对数。

题解

对于环形，我们首先的想法肯定是破环成链，然而，这道题直接把环展开成两倍的话比较复杂，因为对于一对数，从环的两边都可以的话只能算一次，而有些对是两次，有些对是一次。

考虑到本题相比于上题特殊的地方就是环形，我们考虑环的性质，因为最大的一个数只能被相邻的数看到，而一旦有两个数的区间内包含了这个最大数，从链上是看不到的，而从环上是可能看到的。为了消除这种影响，我们考虑把最大的数放在最开头的位置，其他位置循环左移。这样，后面的数可以正常按照上题的方法处理。

还有一种特殊情况，就是这条链的末尾的数可能会看到开头最大的数。我们只需要考虑这种情况，因为假设我们考虑末尾的数看正数第二个数，那么是不可能跨过第一个数看的，所以这种情况已经被包含在链中了，以此类推。所以，我们用一个vis数组记录是否位置\(i\)的数已经统计过了和正数第一个数结对的情况，具体表现为：弹出栈顶的数后，如果栈里只剩下0位置或栈为空，说明已经统计过了。

在一次遍历完成后，我们从右往左再次根据vis数组特判一些情况：如果能够结成对，当前的数应该是末尾到当前位置最大的数，而且vis为0。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int maxx = 0, idx = 0;
    for (int i = 0; i < n; i++) {
        if (maxx < a[i]) {
            maxx = a[i];
            idx = i;
        }
    }
    for (int i = 0; i < n; i++) {
        b[i] = a[(idx + i) % n];
    }
    vector<int> stk;
    vector<bool> vis(n);
    vector<int> cnt(n, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && b[i] >= b[stk.back()]) {
            ans += cnt[stk.back()];
            if (b[i] == b[stk.back()]) {
                cnt[i] = cnt[stk.back()] + 1;
            }
            stk.pop_back();
        }
        if (!stk.empty()) {
            ans++;
            if (stk.back() == 0) {
                vis[i] = 1;
            }
        } else {
            vis[i] = 1;
        }
        stk.push_back(i);
    }
    maxx = b[n - 1];
    for (int i = n - 1; i >= 1; i--) {
        if (b[i] >= maxx && !vis[i]) {
            ans++;
        }
        maxx = max(maxx, b[i]);
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

单调栈 + 二分

奶牛排队

给定\(n\)个奶牛和身高，定义合法的区间的开头是这一段区间的奶牛的身高最小值，区间的结尾是身高的最大值，且中间的奶牛的身高均在最小值和最大值之间（不包括最小值和最大值），求区间最大长度是多少。

题解

我们不妨从左往后遍历时钦定最大值，那么一个区间的最小值的位置就应该是从右往左第一个后缀最大值的位置（假设还没有把当前的数加入到栈里）的右边离它最近的后缀最小值。理解一下这句话：因为最大值已经确定了，所以我们要在前面的位置找到一个最小值，因为题目要求中间的奶牛的身高均在二者之间，所以我们找到第一个后缀最大值（这个值应该是大于等于当前钦定的最大值的），最小值一定出现在它的右边，否则区间就会包含这个数，就会大于等于钦定的最大值，不符合题意；同时，最小值一定是离它最近的后缀最小值，这是因为我们要求最大值，虽然它右边的后缀最小值都是符合题意的，但是显然长度最长需要离它最近。

我们考虑维护两个栈，一个单调递增，用来找后缀最大值，一个单调递减，用来找到后缀最小值，然后从左往后钦定最大值，弹出栈顶的数后，单调递增栈的栈顶就应该是第一个后缀最大值，我们就要找到离它最近的前缀最小值，换句话说，就是第一个位置在它前面的前缀最小值，所以我们在单调递减栈上二分查找（所以我们不用stack来当作栈，而使用vector模拟栈。）

注意细节，单调递增栈是可以有相同元素的，否则与钦定的最大值相同的元素就可能作为前缀最小值，而单调递减栈是不能有相同元素的，否则离后缀最大值最近的元素不能作为区间左端点。同时，二分查找时，单调递增栈可能为空，这时说明当前的数是最大的，所以单调递增栈栈底元素可以作为答案，需要特判。而单调递减栈是空的话，说明当前的数是目前的最小值，答案就是0，在二分时也应该特判掉。

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    vector<int> stk1, stk2;
    for (int i = 0; i < n; i++) {
        while (!stk1.empty() && a[i] <= a[stk1.back()]) {
            stk1.pop_back();
        }
        while (!stk2.empty() && a[i] > a[stk2.back()]) {
            stk2.pop_back();
        }
        int val = stk2.empty() ? -1 : stk2.back();
        int pos = upper_bound(stk1.begin(), stk1.end(), val) - stk1.begin();
        if (pos != stk1.size()) {
            ans = max(ans, i - stk1[pos] + 1);
        }
        stk1.push_back(i);
        stk2.push_back(i);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Atcoder Beginner Contest 379 F

题意

给定\(n\)座楼和它们的高度\(h_i\)，如果\(i\)能看见\(j\)（\(i<j\)），需要满足\(i,j\)之间不存在比\(j\)高的楼。现在给定\(q\)次询问，每次询问给定两个位置\(l,r\)，求第\(r+1\)到\(n\)座有多少座能被\(l,r\)同时看见。

题解

对于一座楼来说，我们关心的是比它高的楼，这可以用单调栈来处理。

接下来，我们考虑两座楼同时能看见需要满足什么条件。发现\(r\)右边的楼能被\(l\)看见，需要满足\(l,r\)之间的最高楼的高度小于等于\(r\)右边的楼。那么我们考虑将\(q\)次询问按照右端点从右到左的顺序排序从而离线处理。

我们从右到左维护一个单调栈（从栈顶到栈底是非递减的），那么对于每一次询问，我们都可以知道\(r\)能够看见的所有楼。我们只需要在这个单调栈里找到第一个比\(l,r\)之间最高的楼还高（或相等）的楼。

对于找到区间最值，我们想到了ST表处理，而要找到第一个大于条件的数，我们自然想到了在单调栈中二分。不过这里的单调栈是从左到右递减的，我们的二分策略需要相应调整一下，应该为上取整，满足条件后更新左边界。

除此之外，我们还需要特判一些情况：比如单调栈中没有比最高楼还高的楼，此时答案是0，还有栈为空的情况直接跳过。

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct ST {
    const int n, k;
    vector<int> in1;
    vector<vector<int>> Max;
    ST(int n) : n(n), in1(n + 1), k(log2(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in1[i];
        }
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = log2(r - l + 1);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> h(n), res(q);
    vector<vector<int>> query(q, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    ST st(n);
    for (int i = 0; i < n; i++) {
        st.in1[i + 1] = h[i];
    }
    st.init();
    for (int i = 0; i < q; i++) {
        cin >> query[i][0] >> query[i][1];
        query[i][0]--, query[i][1]--;
        query[i][2] = i;
    }
    sort(query.begin(), query.end(),
         [&](const vector<int>& i, const vector<int>& j) {
             if (i[1] != j[1]) {
                 return i[1] > j[1];
             }
             return i[0] > j[0];
         });
    int last = n - 1;
    vector<int> stk;
    for (int i = 0; i < q; i++) {
        int l = query[i][0], r = query[i][1], idx = query[i][2];
        for (int j = last; j > r; j--) {
            while (!stk.empty() && h[j] > h[stk.back()]) {
                stk.pop_back();
            }
            stk.push_back(j);
        }
        if (stk.empty()) {
            res[idx] = 0;
            continue;
        }
        int mx = st.getMax(min(l + 2, n), min(r + 1, n));
        int lo = 0, hi = stk.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (h[stk[mid]] >= mx) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        if (h[stk[lo]] < mx) {
            lo--;
        }
        res[idx] = lo + 1;
        last = r;
    }
    for (int i = 0; i < q; i++) {
        cout << res[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}