长的后缀使得区间最小值均 $> a_i$。

具体做法：在 $[1, L_i-1]$ 上二分，用 RMQ（ST 表）查询区间最小值，找到最远的左端点 $p$ 使得 $\min[p, L_i-1] > a_i$。新的“左延伸长度”为 $res = (L_i - p) + (i - L_i)$。

贡献为 $a_i \times res \times (R_i - i)$，加到 $f[L_i]$ 上。

$i = R_j$ 的处理

同理，在 $[R_i+1, n]$ 上二分找到最远的右端点 $q$ 使得 $\min[R_i+1, q] > a_i$。新的“右延伸长度”为 $res = (q - R_i) + (R_i - i)$。

贡献为 $a_i \times (i - L_i) \times res$，加到 $f[R_i]$ 上。

RMQ 预处理

使用 ST 表，st[i][j] 表示从 $i$ 开始长度 $2^j$ 的区间最小值。

查询 $[l, r]$ 的最小值：令 $k = \lfloor \log_2(r-l+1) \rfloor$，则：

复杂度

• 单调栈求 $L_i, R_i$：$O(n)$
• ST 表预处理：$O(n \log n)$
• 差分区间的加：$O(n)$
• 处理 $i=L_j$ 和 $i=R_j$ 时二分 + RMQ：每次 $O(\log n)$，总计 $O(n \log n)$

总复杂度 $O(n \log n)$，可以满足 $n \le 5\times 10^5$，$\sum n \le 10^6$ 的限制。

参考代码

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

const int N = 1e6 + 10;
typedef long long ll;
#define int ll

int T, n, a[N];
int st[N][20];
int L[N], R[N];
int f[N];
int f_sum[N];

void add(int l, int r, int d) {
    if (l <= r) f_sum[l] += d, f_sum[r + 1] -= d;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        st[i][0] = a[i];
        f[i] = f_sum[i] = 0;
    }

    for (int j = 1; j < 20; ++j)
        for (int i = 1; i + (1 << (j - 1)) <= n; ++i)
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

    auto RMQ = [&](int l, int r) {
        int k = log2(r - l + 1);
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    };

    stack<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (stk.size() && a[stk.top()] > a[i]) stk.pop();
        L[i] = stk.size() ? stk.top() : 0;
        stk.push(i);
    }

    while (stk.size()) stk.pop();

    for (int i = n; i; --i) {
        while (stk.size() && a[stk.top()] > a[i]) stk.pop();
        R[i] = stk.size() ? stk.top() : n + 1;
        stk.push(i);
    }

    for (int j = 1; j <= n; ++j) {
        add(1, L[j] - 1, a[j] * (j - L[j]) * (R[j] - j));
        add(R[j] + 1, n, a[j] * (j - L[j]) * (R[j] - j));
        add(L[j] + 1, j - 1, a[j] * (j - 1 - L[j]) * (R[j] - j));
        add(j + 1, R[j] - 1, a[j] * (j - L[j]) * (R[j] - 1 - j));
    }

    for (int i = 1; i <= n; ++i) f[i] = (f_sum[i] += f_sum[i - 1]);

    for (int i = 1; i <= n; ++i) {
        int l = 1, r = L[i] - 1, res = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (RMQ(mid, L[i] - 1) > a[i]) res = L[i] - mid, r = mid - 1;
            else l = mid + 1;
        }
        res += i - L[i];
        f[L[i]] += a[i] * res * (R[i] - i);
    }

    for (int i = 1; i <= n; ++i) {
        int l = R[i] + 1, r = n, res = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (RMQ(R[i] + 1, mid) > a[i]) res = mid - R[i], l = mid + 1;
            else r = mid - 1;
        }
        res += R[i] - i;
        f[R[i]] += a[i] * (i - L[i]) * res;
    }

    for (int i = 1; i <= n; ++i) cout << f[i] << ' ';
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--) solve();
    return 0;
}