Codeworks round 783 (Div. 2) d problem solution

D. Optimal Partition

The question ：
Here you are. $n$ Array of Numbers , You can divide this array into Several consecutive subarrays , Can't be empty .

hypothesis $s[i]$ by $a$ Array of Prefixes and arrays
that Continuous subarray $a_l$ $a_{l+1}$ …$a_r$ Of value by

• $r-l+1$ Premise yes ： $s[r]-s[l-1]>0$
• $0$ Premise yes ： $s[r]-s[l-1]=0$
• $-(r-l+1)$ Premise yes ： $s[r]-s[l-1]<0$

Find the of several continuous subarrays The maximum value of the sum of values

Ideas ：

hypothesis $f[i]$ Express Only the front of the array is considered i The sum of the maximum value of the number .
From the meaning of the title have to

• $f[i]=f[j]+(i-j),[s[i]-s[j]>0,j<i]$
• $f[i]=f[j],[s[i]-s[j]=0,j<i]$
• $f[i]=f[j]-(i-j),[s[i]-s[j]<0,j<i]$

Time complexity $O{n}^2$

Consider optimizing , The above three formulas are further Simplification by

• $f[i]-i=f[j]-j,[s[i]>s[j],j<i]$
• $f[i]=f[j],[s[i]=s[j],j<i]$
• $f[i]+i=f[j]+j,[s[i]<s[j],j<i]$

consider The first formula ,
$f[i]-i=f[j]-j,[s[i]>s[j],j<i]$
Equivalent to
$f[i]=max(f[j]-j)+i,[s[j]<s[i],j<i]$

We can take all of them $s[i]$ As the subscript of the array ,
Equivalent to For each $i$, Query all Less than $s[i]$ This Subscript $f[j]-j$ The maximum of

consider $s[i]$ Too much scope , Cannot be used as an array subscript , We can Will all $s[i]$ discretization
Then query all Less than $s[i]$ This Subscript $f[j]-j$ The maximum of To update $f[i]$

Then on this line segment tree Update subscript to $s[i]$ The value of is $f[i]-i$

The second and third expressions are the same

We can Build three segment trees ,
The maximum value of the query interval , Single point modification , that will do

Time complexity ：$Onlogn$

#include <bits/stdc++.h>
#define fer(i,a,b) for(re i = a ; i <= b ; ++ i)
#define der(i,a,b) for(re i = a ; i >= b ; -- i)
#define cf int _; cin>> _; while(_--)
#define all(x) (x).begin(),(x).end()
#define sf(x) scanf("%lld",&x)
#define re register int
#define lb lower_bound
#define int long long 
#define pb push_back
using namespace std;
const int N = 5e5 + 10 , M = 1e9 , mod = 1e9 + 7 ; // mod = 998244353 ;
const double eps = 1e-7 , pi = acos(-1.0) ;

int n ;
int a[N] , s[N] ;
int f[N] ;
vector<int> q ;

struct Node
{
    
    int l, r;
    int v ;  //  Section [l, r] Maximum of 
}tr[3][N * 4];
int d ;
 
int get(int x)
{
    
    return lb(all(q) , x) - q.begin() + 1 ;
}

void pushup(int u)  //  Information from child nodes , To calculate the information of the parent node 
{
    
    tr[d][u].v = max(tr[d][u<<1].v,tr[d][u<<1|1].v);
}
 
void build(int u, int l, int r)
{
    
    if(l == r) 
    {
    
        tr[d][u] = {
    l,r,-M};
    }
    else
    {
    
        tr[d][u] = {
    l,r};
        int mid = r + l >> 1 ;
        build(u << 1 , l , mid );
        build(u << 1 | 1 , mid + 1 , r);
        pushup(u) ;
    }
}
 
int query(int u, int l, int r)
{
    
    if(tr[d][u].l >= l && tr[d][u].r <= r) 
        return tr[d][u].v ;
    
    int v = -1e9 , minv = 1e9 ;
    int mid = tr[d][u].l + tr[d][u].r >> 1 ;
    if(l <= mid) 
    {
    
        v = max(v,query(u << 1 , l ,r)) ; 
    }
    if(r > mid) 
    {
    
        v = max(v,query(u << 1 | 1 , l , r)) ;
    }
    
    return v ;
}
 
void modify(int u, int x, int v)
{
    
    if(tr[d][u].l == x && tr[d][u].r == x) tr[d][u].v = max(v , tr[d][u].v) ;
    else
    {
    
        int mid = tr[d][u].l + tr[d][u].r >> 1 ;
        if(x <= mid) modify(u << 1 , x , v);
        else modify(u << 1 | 1 , x ,v);
        pushup(u);
    }
}

signed main()
{
    
    cf
    {
    
        cin >> n ;
        fer(i,1,n) sf(a[i]) , s[i] = s[i - 1] + a[i] ;
        fer(i,0,n) f[i] = -1e9 ;
        f[0] = 0 ;
        q.clear() ;
        fer(i,0,n) q.pb(s[i]) ;
        sort(all(q)) ;
        q.erase( unique(all(q)) , q.end() ) ;
        
        // d=0/1/2 Represent three segment trees respectively 
        fer(i,0,2)
        {
    
            d = i ;
            build(1 , 1 , n + 1) ;
        }
        fer(i,0,2)
        {
    
            d = i ;
            modify(1 , get(s[0]) , 0) ;
        }
        
        fer(i,1,n)
        {
    
            int w = get(s[i]) ;
            
            d = 0 ;
            f[i] = query(1 , 1 , w - 1) + i ;
            
            d = 1 ;
            f[i] = max(f[i] , query( 1 , w , w ) ) ;
            
            d = 2 ;
            f[i] = max(f[i] , query( 1 , w + 1 , n + 1) - i ) ;
            
            d = 0 ;
            modify(1 , w , f[i] - i) ;
            
            d = 1 ;
            modify(1 , w , f[i]) ;
            
            d = 2 ;
            modify(1 , w , f[i] + i) ;
        }
    
        cout << f[n] << "\n" ;
    }
    return 0 ;
}