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

Question

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

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

Если 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])

0

algorithm c++optimization segments

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Алгоритм

Во-первых, вы можете найти максимальное значение 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)

0