0

我正在做一个问题，其中需要找到段中最大元素的总和 - 段中最小元素的总和。我尝试使用稀疏表，但时间限制慢了两个。所以我做了类似的事情这个：

如果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])

4

1 回答 1

0

我们可以尝试完成第一个问题，即所有段的最大值之和。

算法

首先，您可以在整个序列中找到最大值 a[i]。将考虑包含 a[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)
于 2012-12-03T12:54:57.187 回答