AC代碼：

?https://codeforces.com/contest/1788/submission/195085759

題意：

給你一個n個整數(shù)的數(shù)組a1，a2，…，an。將S視為滿足以下條件的一組線段。

1. S的每個元素都應(yīng)該是[x，y]形式，其中x和y是1和n之間的整數(shù)，包括1和n，x≤y。

2. S中沒有兩個線段彼此相交。兩段[a，b]和[c，d]相交當且僅當存在整數(shù)x使得a≤x≤b且c≤x≤d。

3. 對于S中的每個[x，y]，ax+ax+1+…+ay≥0。

線段[x，y]的長度定義為y?x+1。f(S)被定義為S中每個元素的長度之和。

形式定義，f(S)=∑[x，y]∈S（y?x+1）。

注意，如果S為空，則f(S)為0。

題解：

DP + 前綴和 + 樹狀數(shù)組