题目链接

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000;

int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
    if (l + 1 == r) {
        ans += a[l];
        return;
    }
    int mid = (l + r) >> 1;
    std::vector<int> pre(a + mid, a + r);
    for (int i = 1; i < r - mid; ++i) pre[i] = std::max(pre[i], pre[i - 1]);
    std::vector<long long> sum(r - mid + 1);
    for (int i = 0; i < r - mid; ++i)
        sum[i + 1] = sum[i] + pre[i];
    for (int i = mid - l, j = mid, max = 0; i >= l; --i) {
        while (j < r && a[j] < a[i]) ++j;
        max = std::max(max, a[i]);
        ans +=(long long)(j - mid) * max;
        ans += sum[r - mid] - sum[j - mid]
;
    }
    solve(l, mid);
    solve(mid, r);
}

int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    solve(0,n);
    std::cout << ans << std::endl;
    return 0;
}

将正解代码填入后，输入

4

1 2 1 2

输出的答案为21

而题目中的答案应为18

求dalao指教