The 2011 Southwestern Europe Regional Contest G, UVa-12393 : Non-negative Partial Sums

問題概要

長さN(<10^6)の数列が与えられる。任意のi<=Nに対して、sum_{0<=k

考えたこと

• 部分和なので累積和が考えやすい。
• サイクリックになっているのは長さを2倍にした数列を考えてやれば良い。
• 長さ2倍の数列で累積和を考えてやれば、長さNの範囲で累積和の最小値が直前の累積和以上になっていればOKだと判定できる。
• つまり必要なのはRMQ。
• sparse tableのRMQは速いがメモリが厳しい。segment treeのRMQはTLEが怖い。
• 区間の長さが固定なんだからこれは蟻本に載ってたスライド最小値か、これならO(N)で解ける。