D. Optimal Partition 线段树优化dp

题目link
参考

思路

考虑 $f[i]$ 为以$i$结尾的最大价值 ,$s[i]$ $a[]$ 的前缀和数组
容易想到
$$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}$$

时间复杂度为 $O(n^2)$
考虑优化
上式即求
$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$

便可用$3$棵线段树来分别维护 $f[j]+j,f[j],f[j]-j$的最大值
用 $s[i]$ 来代表线段树数组下标 由于$s[i]$ 很大考虑进行离散化$s[i]$
注意以下细节
除$0$外 $f$ 要初始化为 $-inf$
建树大小为 $n+1$ 是因为有前缀和小于$0$,因此还要维护 $s[0]=0$ 的值,

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


struct tree{
    
    int l,r;
    int dat; // 线段树中要维护的信息;
    #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;
}