Codeforces Round ＃783 (Div. 2) D题解

D. Optimal Partition

题意：
给你$n$个数的数组,你可以把这个数组分为若干个连续的子数组,不能为空。

假设$s[i]$为$a$数组的前缀和数组
那么连续子数组$a_l$ $a_{l+1}$ …$a_r$的价值为

• $r-l+1$ 前提是： $s[r]-s[l-1]>0$
• $0$ 前提是： $s[r]-s[l-1]=0$
• $-(r-l+1)$ 前提是： $s[r]-s[l-1]<0$

求若干个连续的子数组的价值之和的最大值

思路：

假设$f[i]$表示只考虑数组的前i个数的最大价值之和。
由题意得

• $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]$

时间复杂度$O{n}^2$

考虑优化，将上述三个式子进一步化简为

• $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]$

考虑第一个式子,
$f[i]-i=f[j]-j,[s[i]>s[j],j<i]$
等价于
$f[i]=max(f[j]-j)+i,[s[j]<s[i],j<i]$

我们可以把所有的$s[i]$当做数组的下标,
等价于对每一个$i$,查询所有的小于$s[i]$这个下标的$f[j]-j$的最大值

考虑$s[i]$的范围过大,无法作为数组下标,我们可以将所有的$s[i]$离散化
然后查询所有的小于$s[i]$这个下标的$f[j]-j$的最大值来更新$f[i]$

然后在这颗线段树上更新下标为$s[i]$的值为$f[i]-i$

第二个和第三个式子同理

我们可以建立三颗线段树，
查询区间最大值,单点修改,即可

时间复杂度：$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 ;  // 区间[l, r]中的最大值
}tr[3][N * 4];
int d ;
 
int get(int x)
{
    
    return lb(all(q) , x) - q.begin() + 1 ;
}

void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{
    
    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分别表示三颗线段树
        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 ;
}