均衡区间

两个单调栈，一个维护最大值，一个维护最小值。

考虑固定 $i$，单调栈扫过 $1 \ldots i - 1$，首先弹栈，单调栈中两个值相同时不弹栈，但先不把 $i$ 压栈

令区间左端点为 $j$ 令 $x = \min{(\text{最靠近}i\text{的满足值\textcolor{red}{严格}}>a_i\text{的位置},\text{最靠近}i\text{的满足值\textcolor{red}{严格}}<a_i\text{的位置})}-1$ 必然 $j \le x$，否则必然不满足条件 如果 $j$ 是单调栈中的一个节点，则也一定不满足条件 所以 $\text{以}i\text{为右端点的区间数量}=x-|\text{维护最大值的单调栈}|-|\text{维护最小值的单调栈}|+|\text{维护最大值的单调栈} \cap \text{维护最小值的单调栈}|$

其实维护最大值的单调栈是指的严格大于 $a_i$ 的部分，最小栈同理

求以 $i$ 开头的区间完全镜像

具体看代码

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T, class U>
inline bool chmax(T& a, const U& b)
{
    return a < b ? a = b, true : false;
}
template<class T, class U>
inline bool chmin(T& a, const U& b)
{
    return a > b ? a = b, true : false;
}
constexpr size_t N = 1000005;
int n;
int a[N];
int sta1[N], top1;
int sta2[N], top2;
int l[N], r[N];
bool flag[N];
int tree[N];
void add(int i, int v)
{
    while (i <= n)
    {
        tree[i] += v;
        i += i & -i;
    }
}
int query(int i)
{
    int res = 0;
    while (i > 0)
    {
        res += tree[i];
        i &= i - 1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("interval.in", "r", stdin);
    freopen("interval.out", "w", stdout);
    cin >> n >> a[0];
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        while (top1 > 0 && a[sta1[top1]] < a[i])
        {
            if (flag[sta1[top1]])
            {
                add(sta1[top1], -1);
                flag[sta1[top1]] = false;
            }
            top1--;
        }
        while (top2 > 0 && a[sta2[top2]] > a[i])
        {
            if (flag[sta2[top2]])
            {
                add(sta2[top2], -1);
                flag[sta2[top2]] = false;
            }
            top2--;
        }
        int p1 = lower_bound(sta1 + 1, sta1 + top1 + 1, a[i], [](int pos, int v){return a[pos] > v;}) - sta1 - 1;
        int p2 = lower_bound(sta2 + 1, sta2 + top2 + 1, a[i], [](int pos, int v){return a[pos] < v;}) - sta2 - 1;
        if (p1 > 0 && p2 > 0)
        {
            int x = min(sta1[p1], sta2[p2]) - 1;
            int a = upper_bound(sta1 + 1, sta1 + top1 + 1, x) - sta1 - 1;
            int b = upper_bound(sta2 + 1, sta2 + top2 + 1, x) - sta2 - 1;
            r[i] = x - a - b + query(x);
        }
        sta1[++top1] = i;
        sta2[++top2] = i;
        add(i, 1);
        flag[i] = true;
    }
    top1 = top2 = 0;
    memset(tree + 1, 0, sizeof(int) * n);
    memset(flag + 1, 0, sizeof(bool) * n);
    for (int i = n; i >= 1; i--)
    {
        while (top1 > 0 && a[sta1[top1]] < a[i])
        {
            if (flag[sta1[top1]])
            {
                add(n - sta1[top1] + 1, -1);
                flag[sta1[top1]] = false;
            }
            top1--;
        }
        while (top2 > 0 && a[sta2[top2]] > a[i])
        {
            if (flag[sta2[top2]])
            {
                add(n - sta2[top2] + 1, -1);
                flag[sta2[top2]] = false;
            }
            top2--;
        }
        int p1 = lower_bound(sta1 + 1, sta1 + top1 + 1, a[i], [](int pos, int v){return a[pos] > v;}) - sta1 - 1;
        int p2 = lower_bound(sta2 + 1, sta2 + top2 + 1, a[i], [](int pos, int v){return a[pos] < v;}) - sta2 - 1;
        if (p1 > 0 && p2 > 0)
        {
            int x = max(sta1[p1], sta2[p2]) + 1;
            int a = upper_bound(sta1 + 1, sta1 + top1 + 1, x, greater<>()) - sta1 - 1;
            int b = upper_bound(sta2 + 1, sta2 + top2 + 1, x, greater<>()) - sta2 - 1;
            l[i] = n - x + 1 - a - b + query(n - x + 1);
        }
        sta1[++top1] = i;
        sta2[++top2] = i;
        add(n - i + 1, 1);
        flag[i] = true;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << l[i] << " \n"[i == n];
    }
    for (int i = 1; i <= n; i++)
    {
        cout << r[i] << " \n"[i == n];
    }
    return 0;
}