CF：1667B. Optimal Partition（dp好题：线段树优化dp）

题目链接
题 面 ： 题面： 题面：

题 意 ： 题意： 题意：
给定一个长度为n的数组，将其分成若干个连续的子数组。求每个子数组的价值之和的最大值。
每个子数组的价值：
对于 s ( l , r ) = a l + a l + 1 + . . . + a r s(l,r)=a_l+a_{l+1}+...+a_r s(l,r)=al​+al+1​+...+ar​
若 s ( l , r ) > 0 , 则 价 值 为 r − l + 1 若s(l,r)>0,则价值为r-l+1 若s(l,r)>0,则价值为r−l+1
若 s ( l , r ) = 0 ， 则 价 值 为 0 若s(l,r)=0，则价值为0 若s(l,r)=0，则价值为0
若 s ( l , r ) < 0 ， 则 价 值 为 − ( r − l + 1 ) 若s(l,r)<0，则价值为-(r-l+1) 若s(l,r)<0，则价值为−(r−l+1)

题 解 ： 题解： 题解：
题解链接

#include 
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef pair PII;
typedef pair PDD;
typedef long long LL;
#define int LL
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        s=(s<<1)+(s<<3)+(ch-'0');
        ch=getchar();
    }
    return s*w;
}
const int maxn=5e5+5;
const int inf=0x3f3f3f3f3f3f3f;
int n;
int a[maxn];
int s[maxn];
int f[maxn];
struct Node{
    int l,r;
    int val[3];
}tr[maxn<<2];
vector head;
int get_pos(int x){
    return lower_bound(head.begin(),head.end(),x)-head.begin();
}
void pushup(int u){
    for(int i=0;i<3;i++) tr[u].val[i]=max(tr[u<<1].val[i],tr[u<<1|1].val[i]);
}
void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r){
        for(int i=0;i<3;i++) tr[u].val[i]=-inf;
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int p,int x,int sym){
    if(tr[u].l==tr[u].r){
        tr[u].val[sym]=max(tr[u].val[sym],x);
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(mid>=p) modify(u<<1,p,x,sym);
    if(midr) return -inf;
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].val[sym];
    int mid=tr[u].l+tr[u].r>>1;
    int ans=-inf;
    if(mid>=l) ans=query(u<<1,l,r,sym);
    if(mid>n;
    for(int i=1;i<=n;i++) f[i]=-inf;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    for(int i=0;i<=n;i++) head.push_back(s[i]);
    sort(head.begin(),head.end());
    head.erase(unique(head.begin(),head.end()),head.end());
    int len=head.size();
    build(1,0,len-1);
    for(int i=0;i<3;i++)
        modify(1,get_pos(0),s[0],i);
    for(int i=1;i<=n;i++){
        int l=query(1,0,get_pos(s[i])-1,0)+i;
        int mid=query(1,get_pos(s[i]),get_pos(s[i]),1);
        int r=query(1,get_pos(s[i])+1,len-1,2)-i;
        f[i]=max(l,max(mid,r));
        modify(1,get_pos(s[i]),f[i]-i,0);
        modify(1,get_pos(s[i]),f[i],1);
        modify(1,get_pos(s[i]),f[i]+i,2);
    }
    cout<>t;
    while(t--) solve();
    return 0;
}