Как посчитать сумму min(subarray) * sum(subarray) для всех подмассивов за O(n)

Код не пишу. Но идеи должны помочь.

1 - Если взять минимум на всём массиве, то его "вклад" будет равен сумме значений всех отрезков которые его включают.

2 - Как посчитать эту сумму за O(1). Вычислим стандартные префикс суммы Pr[x]. И вычислим F[x] = sum(i, 0, x) {a[i] * (x-i + 1)}. Потом вычислить тоже самое но в обратную сторону. Дальше всё показываю на примере вперёд. Сумма значений всех отрезков вперёд до точки r, содержащие x это S(r,x) = F[r] - F[x-1] - (r - x + 1) * Pr[x] (Примерно так, уточните в отладчике). F[-1] = 0.

3 - Если обсчитать минимум и "удалить" его из массива, то массив распадается на 2 части. Повторять до конца. Конечно удалять нельзя и нужно быстро находить ближайший слева и справа удалённый элемент. Для этой задачи может помочь любое дерево.

Общая сложность - что-то около O(N log N)

Разделяй и властвуй. Пусть a - массив элементов, j индекс элемента приблизительно в середине a. Тогда разобьём все подмассивы a на три группы: подмассивы слева он j, подмассивы, содержащие индекс j и подмассивы справа от j. Если мы научимся вычислять сумму для всех подмассивов, содержащих j, за линейное время, то за NlogN сумеем вычислить общую сумму для всего массива.

С этого момента считаем сумму только для отрезков, содержащих j. Предположим, что a_j – глобальный минимум в массиве. Если это не так, то вырежем из a такой подмассив, в котором a_j – минимум. В дальнейшем переобозначим этот подмассив как a.

Итак есть a и есть a_j – его минимум.

s_[i,k] = ∑_m∈[i,k] a_m – cумма элементов массива на отрезке [i, k].

S_i,k – сумма всех подмассивов массива a таких, что i ≤ j ≤ k.

S_i,k = ∑_{m∈[i,j],n∈[j,k]} s_[m,n]

S_i,k - S_i,k-1 = ∑_m∈[i,j] s_[m,k] = ∑_m∈[i,j] (s_[m,j-1] + a_j + s_[j+1,k]) =
= ∑_m∈[i,j] s_[m,j-1] + ∑_m∈[i,j] (a_j + s_[j+1,k]) = ∑_m∈[i,j] s_[m,j-1] + (j - i + 1)(a_j + s_[j+1,k]).

Обозначим левое слагаемое Q_i = ∑_m∈[i,j] s_[m,j-1]. Аналогично Q_k = ∑_n∈[j,k] s_[j+1,n]. Обозначения Q_i и Q_k не конфликтуют, так как i ≤ j и j ≤ k.

Тогда S_i,k вычисляется из S_i,k-1 за константу:

S_i,k = S_i,k-1 + Q_i + (j - i + 1)(a_j + s_[j+1,k]).

В целом переход от k - 1 к k выглядит как:

s_[j+1,k] = s_[j+1,k-1] + a_k
Q_k = Q_k-1 + s_[j+1,k]
S_i,k = S_i,k-1 + Q_i + (j - i + 1)(a_j + s_[j+1,k]).

Аналогичный переход от i + 1 к i:

s_[i,j-1] = a_i + s_[i+1,j-1]
Q_i = Q_i+1 + s_[i,j-1]
S_i,k = S_i+1,k + (k - j + 1)(s_[i,j-1] + a_j) + Q_k.

Оба перехода делаются за константу. В целом за линейное время мы соберём сумму всех подмассивов по всему массиву.

Напомню что a_j до сих пор предполагается глобальным минимумом. И найденную сумму надо будет домножить на a_j.

Что делать когда отрезок массива a, на котором a_j – глобальный минимум, исчерпан? Разберу случай когда этот отрезок с обоих концов ограничен элементами, которые меньше a_j. Из этих элементов надо выбрать максимум, обновить наш "минимум" и продолжить "экспансию" на большем отрезке. Процесс повторять пока не будет обработан весь массив.

Обработка займёт линейное время. Если вы сюда пробрались через лес сомнительных обозначений, вас ждёт награда – решение за NlogN:

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

size_t a_size = 0;
size_t a_capacity = 0;
int32_t *a_data = NULL;

void read_a() {
    int32_t ai;
    while (scanf("%" SCNd32, &ai) == 1) {
        if (a_capacity == a_size) {
            size_t capacity = 2 * a_size + 1;
            int32_t *data = realloc(a_data, sizeof(*a_data) * capacity);
            if (data == NULL) {
                exit(1);
            }
            a_capacity = capacity;
            a_data = data;
        }
        a_data[a_size++] = ai;
    }
}

void release_a() {
    a_size = 0;
    a_capacity = 0;
    free(a_data);
}

int32_t mod(int64_t x) {
    const int32_t mod = 1000000007;
    int32_t y = (int32_t)(x % mod);
    return (y >= 0) ? y : mod + y;
}

int32_t add(int32_t a, int32_t b) {
    return mod(a + b);
}

int32_t mul(int32_t a, int32_t b) {
    return mod((int64_t)a * b);
}

int32_t dc_a(const int32_t ii, const int32_t kk) {
    if (ii + 1 == kk) {
        return 0;
    }

    const int32_t j = ii + (kk - ii) / 2;

    int32_t level = a_data[j];
    int32_t s = mul(a_data[j], a_data[j]);

    int32_t si1 = 0;
    int32_t si2 = 0;
    int32_t i = j - 1;

    int32_t sk1 = 0;
    int32_t sk2 = 0;
    int32_t k = j + 1;

    for (; ; ) {
        /* expand left */
        while (ii < i && a_data[i] >= level) {
            si1 = add(si1, a_data[i]);
            si2 = add(si2, si1);
            s = add(s, mul(level, add(sk2, mul(k - j, add(a_data[j], si1)))));
            --i;
        }

        /* expand right */
        while (k < kk && a_data[k] >= level) {
            sk1 = add(sk1, a_data[k]);
            sk2 = add(sk2, sk1);
            s = add(s, mul(level, add(si2, mul(j - i, add(a_data[j], sk1)))));
            ++k;
        }

        /* update level */
        if (ii < i) {
            if (k < kk) {
                /* level = max(a_data[i], a_data[k]); */
                level = (a_data[i] < a_data[k]) ? a_data[k] : a_data[i];
            } else {
                level = a_data[i];
            }
        } else {
            if (k < kk) {
                level = a_data[k];
            } else {
                break;
            }
        }
    }

    return add(s, add(dc_a(ii, j), dc_a(j, kk)));
}

int main() {
    read_a();
    printf("%" PRId32 "\n", dc_a(-1, (int32_t)a_size));
    release_a();
}

$ gcc -O3 dc.c

$ time -p seq 10000000 | ./a.out
143284477
real 2.64
user 2.65
sys 0.06