c - SPOJ これらの質問に答えていただけますか I

Question

SPOJでこの問題を解決しようとしています。セグメント ツリー セクションでこの問題を見つけたので、セグメント ツリーを使用する解決策が考えられると確信しています。しかし、ツリー ノードに格納する必要があるメタデータを思い付くことができません。最大合計はKadane のアルゴリズムを使用して計算できます. しかし、セグメントツリーを使用してそれを計算する方法。範囲のアルゴの出力のみを保存すると、その特定の範囲のクエリには正しいが、親がその値を使用するのは正しくありません。負の合計プレフィックスや負の合計サフィックスなどの情報をさらに保存するとします。私はいくつかのテストケースを解決することができます。しかし、それは完全に正しいわけではありません。この特定の問題を解決するためにメタデータにどのようにアプローチすればよいかについて、いくつかの指針を教えてください。助けてくれてありがとう。

Answer 1

接頭辞の合計にセグメントツリーを構築することで解決できます

sum[i] = sum[i - 1] + a[i] 

次に、次の情報をノードに保持します。

node.min   = the minimum sum[i], x <= i <= y 
            ([x, y] being the interval associated to node)
           = minimum(node.left.min, node.right.min)
node.max   = same but with maximum

node.best  = maximum(node.left.best,
                     node.right.best,
                     node.right.max - node.left.min
                    )

基本的に、このbestフィールドは、関連付けられた間隔の最大合計部分配列の合計を示します。これは、2 つの子ノードの最大合計部分配列の 1 つ、または両方の子区間を横切るシーケンスのいずれかです。これは、右の子の最大値から左の子の最小値を減算することによって得られます。可能な線形解:sum[j], j < i各 each の最小値を見つけてから、グローバルな最大値とi比較します。sum[i] - sum[j]

ここで、クエリに答えるには、関連付けられた間隔がクエリされた間隔を構成するノードを検討し、ツリーを構築した方法と同様のことを行う必要があります。自分で調べてみてください。でも、どこかで行き詰まったら教えてください。