0

セグメント内の最大要素の合計 - セグメント内の最小要素の合計を見つける必要があるという問題を解決しています。 Sparse Table を使用してみましたが、時間制限が 2 つ遅いため、次のようなことをしました。これ：

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））を加えたもの。そして、問題は2つの小さなシーケンス[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 に答える