算法竞赛模板

https://atcoder.jp/contests/abc407/tasks/abc407_f

对于每个a[i]点算 对答案区间的贡献，发现是一个两个等差数列区间， 最后跑两遍前缀和即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cout << #x << " " << x << endl 
#define int ll 
const int N = 2e5 + 10;
int n;
int a[N], s[N], R[N], L[N], ans[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    stack<int> stk;
    a[0] = a[n+1] = 1e9;
    stk.push(0);
    for (int i = 1; i <= n; i++) {
        while (stk.size() && a[i] > a[stk.top()]) stk.pop();
        L[i] = stk.top() + 1;
        stk.push(i);
    }
    while (stk.size()) stk.pop();
    stk.push(n+1);
    for (int i = n; i >= 1; i--) {
        while (stk.size() && a[i] >= a[stk.top()]) stk.pop();
        R[i] = stk.top() - 1;
        stk.push(i);
    }
    for (int i = 1; i <= n; i++) {
        int l = L[i], r = R[i];
        auto [mi, mx] = minmax({i - l + 1, r - i + 1});
        int len = r - l + 1;
        ans[1] += a[i], ans[mi+1] -= a[i], ans[mx+1] -= a[i], ans[len+2] += a[i];
    }
    for (int i = 1; i <= n+2; i++) ans[i] += ans[i-1];
    for (int i = 1; i <= n+2; i++) ans[i] += ans[i-1];
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
} /* 2025-06-12 12:53 */