D. Optimal partition segment tree optimization DP

subject link
Reference resources

Ideas

consider $f[i]$ For $i$ The greatest value of the ending ,$s[i]$ $a[]$ Prefix and array
Easy to think of
$$f[i]=\{\begin{array}{l}f[j]-j+i,s[i]>s[j]\\ f[j],s[i]=s[j]\\ f[j]+j-i,s[i]<s[j]\end{array}$$

The time complexity is $O(n^2)$
Consider optimizing
The above formula is the solution
$f[i]=max(f[j]-j)+i,s[i]>s[j],j<i$
$f[i]=max(f[j]),s[i]=s[j],j<i$
$f[i]=max(f[j]+j)-i,s[i]<s[j],j<i$

Ready to use $3$ A segment tree to maintain $f[j]+j,f[j],f[j]-j$ The maximum of
use $s[i]$ To represent the subscript of the line segment tree array because $s[i]$ Great consideration is given to discretization $s[i]$
Pay attention to the following details
except $0$ Outside $f$ To initialize to $-inf$
The tree size is $n+1$ Because there is a prefix and less than $0$, Therefore, it is necessary to maintain $s[0]=0$ Value ,

const int inf = 1e18;
const int INF = ~0ULL;
const int N = 500005;


struct tree{
    
    int l,r;
    int dat; //  The information to be maintained in the segment tree ;
    #define ls (i<<1)
    #define rs (i<<1|1)
}t[3][N<<2];
int d;
int f[500005];
void up(int i){
    
    t[d][i].dat = max(t[d][ls].dat,t[d][rs].dat);
}
void build(int i,int l,int r){
    
    t[d][i] = {
    l,r};
    if(l==r){
    
        t[d][i].dat = -inf;
        return ;
    }
    int mid = (l+r) >> 1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(i);
}
void change(int i,int p, int k){
    
    if(t[d][i].l == t[d][i].r){
    
        t[d][i].dat = max(k,t[d][i].dat);
        return;
    }
    int mid = (t[d][i].l + t[d][i].r) >> 1;
    if(p <= mid) change(ls,p,k);
    else change(rs,p,k);
    up(i);
}
int ask(int i,int l,int r){
    
    if(l <= t[d][i].l && r >= t[d][i].r){
    
        return t[d][i].dat;
    }
    int res = -inf;
    int mid = (t[d][i].l+t[d][i].r) >> 1;
    if(l <= mid) res = max(res,ask(ls,l,r)); 
    if(r > mid) res  =  max(res,ask(rs,l,r));
    return res;
}
void solve(){
    
    int n;cin>>n;
    vector<int> a(n),s(n+1,0);
    forr(i,0,n-1) cin>>a[i],s[i+1] = s[i]+a[i];
    forr(i,1,n) f[i] = -inf;
    f[0] = 0;
    auto v = s;
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i = 0;i <= n;i++) s[i] = lower_bound(v.begin(),v.end(),s[i]) - v.begin()+1;

    for(int i = 0; i < 3;i++){
    
        d = i;
        build(1,1,n+1);
    }
    for(int i = 0; i < 3;i++){
    
        d = i;
        change(1,s[0],0);
    }

    int res = -inf;
    forr(i,1,n){
    
        int p = s[i];
        d = 0;
        f[i] = max(f[i],ask(1,1,p-1)+i);
        d = 1;
        f[i] = max(f[i],ask(1,p,p));
        d = 2;
        f[i] = max(f[i],ask(1,p+1,n+1)-i);
        d = 0;
        change(1,p,f[i]-i);
        d = 1;
        change(1,p,f[i]);
        d = 2;
        change(1,p,f[i]+i);
    }
    cout << f[n] << endl;
}



signed main()
{
    
    _orz;
    int t;cin>>t;
    while(t--) solve();
    return 0;
}