Codeforces #783 div2 D. Optimal Partition（dp+离散化+树状数组维护）

题目链接

https://codeforces.com/contest/1668/problem/D

题意

给出一个长度为n的数组a，现在需要将该数组分成任意段
设s为$[a_l,a_r]$中各元素之和，即$a_l+...+a_r$
对于每一段$[a_l,a_r]$，其val为：

$val=r?l+1(s>0)$
$val=0(s==0)$
$val=r?l+1(s>0)$

现在需要求出分成任意段后，各段val值的和最大是多少

分析

这题需要进行状态转移，$dp[i]$ 表示前$i$个元素分段后得到的最大val
不过，对于怎么转移方程，则需要分情况分析了

子段和小于0

结论： 子段和小于0的段，其长度最大只会为1
分析：
若该子段长度大于1
如果其中全是负数，则将其拆成全为1的小段，得到的总val值不变
如果其中存在0或者正数，拆成长度为1的小段肯定能得到更优的总val值

子段和为0

结论： 子段和为0的段，其长度最长也只能会是1
分析：
若该子段长度大于1，我们可以将子段分成长度相等的两段
即$aa...abb...b$ 或者 $aa...akbb...b$（a、b数量相等）
如果a段b段的和都为0，则我们可以将这段继续拆分下去

如果在前一半中存在前缀和小于0的位置，例如：$aa.|..abb...b$
|的前段前缀和小于0，那么我们可以得到|的后端的和就是大于0的

同理，如果在后一半中存在后缀和小于0的位置，例如：$aa...abb.|..b$
|的后面的和小于0，那么我们可以得到|的前端的和就是大于0的

那么我们将该段从 | 的位置分开，得到的val值就肯定大于0，比直接将整段看作0得到的val值更优

将每个段分下去就会发现，最后等于0的段只会是长度为1的 $a[i]$ 为0的段

子段和大于0

对于子段和大于0的段，我们则可以直接进行dp转移
例如对于$...j[...i]$，对于$[]$内的段的状态转移为：$dp[i]=dp[j]+(i?j)$
稍微移一下项：$dp[i]=(dp[j]?j)+i$
可以发现，当前情况只需在确保子段和大于0的条件下，从$dp[j]?j$ 最大转移过来即可

对此，我们可以对前缀和进行离散化，使用树状数组对$dp[j]?j$进行维护，每次求小于当前前缀和（保证差值大于0）的位置中，$dp[j]?j$ 的最大值对 $dp[i]$ 进行更新

代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define PII pair<int,int>
using namespace std;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-8;
const int N=5e5+5;
int n,cnt,dp[N],c[N];
ll a[N],pre[N];
set<ll> st;
map<ll,int> id;
void add(int x,int k)
{
    while(x<=n)c[x]=max(c[x],k),x+=(x&-x);
}
int query(int x)
{
    int cnt=-inf;while(x>0)cnt=max(cnt,c[x]),x-=(x&-x);return cnt;
}
void solve()
{
    cin>>n;cnt=0;   //初始化st.clear(); id.clear();for(int i=1;i<=n;i++)dp[i]=-inf,c[i]=-inf;st.insert(0);for(int i=1;i<=n;i++){
    cin>>a[i];pre[i]=pre[i-1]+a[i];st.insert(pre[i]);}for(ll p:st)  //对前缀和进行离散化id[p]=++cnt;add(id[0],0);   //将起始无元素状态时的0状态加入树状数组中for(int i=1;i<=n;i++){
    if(a[i]<0)dp[i]=dp[i-1]-1;else if(a[i]==0)dp[i]=dp[i-1];dp[i]=max(dp[i],query(id[pre[i]]-1)+i);add(id[pre[i]],dp[i]-i);}cout<<dp[n]<<endl;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}