HILO (USACO Gold 2021 December)

这个题是比较复杂的单调栈的应用，确实比较费脑子。

这个是 $\mathcal{O}(n \log n)$ 的解法（因为map查询是 $\log n$ 的），相对比较好理解，最佳解法是 $\mathcal{O}(n)$ 的。

主要的思想是从纵向（ $x$ 增长的维度）看，所有的数字对应的回答都是 HI..HI LO..LO 这样的pattern。所以每个数字对应三个 $x$ 的值，就是HI开始的 $x$ 值，HI变成LO的 $x$ ，以及LO结束的 $x$ 。
这三个 $x$ 值的计算，可以通过单调栈来完成。 a. 从小到大枚举数字 $0..x$ ， $x$ 对应行和列，HI会变成LO（下面实现中是删除HI，插入LO）。 b. 一个回答LO的数字之后所有更小的数字，都会被跳过。在枚举过程中，把每个数字的位置放到单调增栈上，pop出来的大于当前数字的位置，就是需要delete的位置。 c. 一个回答HI的数字之后所有更大的数字，也都会被跳过。计算HI插入位置的办法，是从大到小枚举数字，将数字位置放到单调增栈上，pop出现大于当前数字的益，就是需要insert HI的位置。所有最后留在栈上的位置，在0的位置插入HI。
新增一个HI/LO或者删除一个HI/LO，对于HILO的数量的影响，是0或者1，这个只依赖于插入位置前后的元素，通过map iterator，这个可以 $\mathcal{O}(\log n)$ 实现。
因为每个数字最多对应 $4$ 个操作，所以最终的复杂度是 $\mathcal{O}(n \log n)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;      // <= 2e5
int p[200005], pos[200005];
vector<int> to_del[200005];             // deletions for each x value
vector<pair<int,char>> to_ins[200005];  // insertions for each x value, and HI/LO to insert
stack<int> st;
map<int, char> m;                       // position -> 'H' / 'L'
 
int hilo(map<int,char>::iterator it, map<int,char>::iterator nxt) {
    return it->second == 'H' && nxt->second == 'L';
}
 
// return the change to number of HILO's from inserting the element at 'it'
// 0 or 1
int diff(map<int,char>::iterator it) {
    int res = 0;
    if (it != begin(m))
        res += hilo(prev(it), it);
    if (next(it) != end(m))
        res += hilo(it, next(it));
    if (it != begin(m) && next(it) != end(m))
        res -= hilo(prev(it), next(it));
    return res;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
        p[i]--;
        pos[p[i]] = i;
    }
    // At i, all numbers <i that appear after i will start to be skipped (deleted).
    // This deletion is generated with a mono-increasing stack of positions (of numbers < i)
    // In this row we also insert a LO for number i.
    for (int i = 0; i < n; i++) {
        while (st.size() && st.top() > pos[i]) {
            to_del[i+1].push_back(st.top());
            st.pop();
        }
        st.push(pos[i]);
        to_ins[i+1].push_back({pos[i], 'L'});
    }
    // Also at i, all numbers >i that appear after i will start to say 'HI'
    // This is done with decreasing i.
    // We also insert a deletion of the series of HI's at number i.
    st = stack<int>();
    for (int i = n-1; i >= 0; i--) {
        while (st.size() && st.top() > pos[i]) {
            to_ins[i+1].push_back({st.top(), 'H'});
            st.pop();
        }
        st.push(pos[i]);
        to_del[i+1].push_back(pos[i]);
    }
    while (st.size()) {
        to_ins[0].push_back({st.top(), 'H'});
        st.pop();
    }
 
    // Make a pass to apply all the changes
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        for (int del: to_del[i]) {
            auto it = m.find(del);
            ans -= diff(it);
            m.erase(it);
        }
        for (pair<int,char> ins: to_ins[i]) {
            auto it = m.insert(ins).first;
            ans += diff(it);
        }
        printf("%d\n", ans);
    }
 
    return 0;
}