Сумма всех Максимум и минимум во всех сегментах

Question

Я делаю задачу, в которой есть необходимость найти сумму максимальных элементов в сегменте - сумму минимальных элементов в сегменте. Я пытался использовать разреженную таблицу, но это два медленных для ограничения по времени. Так что я сделал что-то вроде этот:

Если n=4 сегменты [1,2],[1,3],[1,4],[2,3],[2,4],[3,4], Проблема похожа на проблему RMQ, но я должен сделать это для всех сегментов и найти

sum=max(a[1],a[2])+ max(a[1],a[2],a[3])+max(a[1],a[2],a[3],a[4])+max(a[2],a[3])+m‌​ax(a[2],a[3],a[4])+max(a[3],a[4])-min(a[1],a[2])+min(a[1],a[2],a[3])+min(a[1],a[2‌​],a[3],a[4])+min(a[2],a[3])+min(a[2],a[3],a[4])+min(a[3],a[4])

for(i=1;i<n;i++)
{
    maxtilli[i-1]=INT_MIN;
    mintilli[i-1]=INT_MAX;
    for(k=1,j=i;j<=n;k++,j++)
    {
        if(a[j]>maxtilli[k-1])
        {
            maxtilli[k]=a[j];
        }
        else
        {
             maxtilli[k]=maxtilli[k-1];
        }

        if(a[j]<mintilli[k-1])
        {
            mintilli[k]=a[j];
        }
        else
        {   
            mintilli[k]=mintilli[k-1];
        }
        if(i!=j)
        { 
            ans+=(maxtilli[k]-mintilli[k]);
        }
    }
}

Вот n порядка 100 000 Так есть ли способ оптимизировать его.

предполагать n=4 тогда сегменты [1,2],[1,3],[1,4],[2,3],[2,4],[3,4],

Вещь требуется sum=max(a[1],a[2])+max(a[1],a[2],a[3])+max(a[1],a[2],a[3],a[4])+max(a[2],a[3])+m‌​ax(a[2],a[3],a[4])+max(a[3],a[4])-min(a[1],a[2])+min(a[1],a[2],a[3])+min(a[1],a[2‌​],a[3],a[4])+min(a[2],a[3])+min(a[2],a[3],a[4])+min(a[3],a[4])

Answer 1

Мы можем попытаться завершить первую задачу, суммой максимального значения во всех сегментах.

Алгоритм

Во-первых, вы можете найти максимальное значение a [i] во всей последовательности. Все сегменты, которые содержат [i], будут рассматриваться. Ответ плюс A[i] * (i * (n - i)). И проблема разбита на две небольшие последовательности [1, i - 1] и [i + 1， n], вы можете сделать это таким же образом.

Код

void cal(int L, int R){
    max_index = find_max(L, R); // O(logN), using Sparse Table or Segment Tree
    int all_segments = (max_index - L + 1) * (R - max_index)
    ans += a[max_index] * all_segments;
    cal(L, max_index - 1);
    cal(max_index + 1, R);
}
// call max_index N times, so the total complexity is O(N * logN)