所有的最大的总和与最小各阶层 [英] Sum of all Maximum and minimum in all segments

问题描述

我做一个问题，即有必要找到最大元素之和在一个段 - 使用稀疏表中一个segment.I最小元素总和试过，但它是两个用于时间慢limit.So我的确是这样的：

I am doing a problem in which there is a need to find sum of maximum elements in a segment - sum of minimum elements in a segment.I tried using Sparse Table ,but it is two slow for the time limit.So i did something like this:

如果 N = 4 段 [1,2]，[1,3]，[1,4]，[2,3 ]，[2,4]，[3,4] 。 问题是类似于RMQ问题，但我必须这样做，各阶层，并找到

If n=4 segments are [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]. The problem is similar to an RMQ problem but i have to do it for all segments and find the

和= MAX（一[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])

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 10万的订单。那么，有没有办法优化它。

Here n is of the order of 100,000. So is there any way to optimize it.

假设 N = 4 然后段 [1,2]，[1,3]，[1,4]，[2， 3]，[2,4]，[3,4] 。

需要的东西是 <$c$c>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])

推荐答案

我们可以尝试完成第一个问题，最大的价值之和在所有领域。

We can try to finish the first problem, sum of the max value in all segments.

首先，你可以找到最高值[i]于整个序列。所有的片段，其含有[I]将被考虑。答案加上A [1] *（I *（N - I））。和这个问题被分成两个小的序列[1，I - 1]和[i + 1的，n]的，可以以同样的方式做到这一点

First, you can find the max value a[i] in the whole sequence. All segments which contain a[i] would be considered. The answer plus A[i] * (i * (n - i)). And the problem is split into two small sequences [1, i - 1] and [i + 1， n], you can do it in the same way.

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)

这篇关于所有的最大的总和与最小各阶层的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！