所有分段中所有最大值和最小值的总和

Question

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

如果CCD_ 1段是CCD_。这个问题类似于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的数量级为100000。有什么方法可以优化它吗？

假设CCD_ 5，则分段为CCD_。

需要的是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)