题解：CF75D Big Maximum Sum

· · 题解

温馨提示：本人的代码较长，思路较繁，请谨慎阅读。

很明显的线段树维护最大子段和，先处理出每一个小数组的数据，在放到线段树上面合并即可，合并方式参见 GSS1。

但是这题有一点比较坑，这题中选出来的最大子段不能为空，于是我们需要另外维护一些数据，并且保证选出来至少一个数。然后在求全局最大子段和时就不用向 0 取 \max 了。具体实现可以看代码。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define gc getchar
#define pc putchar
#define sz(v) ((int)(v.size()))
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
    int x=0,f=1;
    char ch=gc();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=gc();}
    return x*f;
}
inline void print(int x){
    if (x<0) pc('-'),x*=-1;
    if (x<10) pc(x+'0');
    else print(x/10),pc(x%10+'0');
}
const int N=55;
const int M=250005;
struct node{
    int len;//小数组的长度
    int lmax,rmax,sum;//小数组前缀和的最大值，后缀和的最大值，以及整个数组的和
    int ma;//最大子段和
    int lmax2,rmax2,ma2;//保证不为空的数据，意义与上面相同
}a[N],t[M<<2];//上面都是 GSS1 的常见操作
int b[M];
void push_up(int p){
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
    t[p].lmax=max(t[ls(p)].lmax,t[ls(p)].sum+t[rs(p)].lmax);
    t[p].rmax=max(t[rs(p)].rmax,t[rs(p)].sum+t[ls(p)].rmax);
    t[p].ma=max(max(t[ls(p)].ma,t[rs(p)].ma),t[ls(p)].rmax+t[rs(p)].lmax);
    t[p].lmax2=max(t[ls(p)].lmax2,t[ls(p)].sum+t[rs(p)].lmax);
    t[p].rmax2=max(t[rs(p)].rmax2,t[rs(p)].sum+t[ls(p)].rmax);
    t[p].ma2=max(max(t[ls(p)].ma2,t[rs(p)].ma2),max(t[ls(p)].rmax2+t[rs(p)].lmax2,max(t[ls(p)].rmax2+t[rs(p)].lmax,t[ls(p)].rmax+t[rs(p)].lmax2)));//这里要注意细节，可能有很多种情况。
    if (p!=1){//不在求全局的时候向 0 取 max
        t[p].lmax=max(t[p].lmax,0ll);
        t[p].rmax=max(t[p].rmax,0ll); 
        t[p].ma=max(t[p].ma,0ll);
    }
}
void build(int p,int pl,int pr){
    if (pl==pr){
        t[p]=a[b[pl]];
        return ;
    }
    int mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    push_up(p);
}
int dp[N];
void sol(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i].len;
        vector<int> v;v.pb(0);
        a[i].lmax=a[i].rmax=a[i].sum=a[i].ma=0;
        a[i].lmax2=a[i].rmax2=a[i].ma2=-1e9;//因为不能为空，所以一开始不能取 0
        for (int j=1;j<=a[i].len;j++){
            int x;
            cin>>x;
            v.pb(x);
            a[i].sum+=x;
        }
        int now=0;
        for (int j=1;j<=a[i].len;j++){
            now+=v[j];
            a[i].lmax=max(a[i].lmax,now);
            a[i].lmax2=max(a[i].lmax2,now);
        }
        now=0;
        for (int j=a[i].len;j>=1;j--){
            now+=v[j];
            a[i].rmax=max(a[i].rmax,now);
            a[i].rmax2=max(a[i].rmax2,now);
        }
        now=0;
        for (int j=1;j<=a[i].len;j++){
            now=max(now+v[j],0ll);
            a[i].ma=max(a[i].ma,now);
        }
        int mx=-1e9;
        for (int j=1;j<=a[i].len;j++){
            mx=max(mx,v[j]);
        }
        if (mx<0) a[i].ma2=mx;//如果整个数组中所有数都 <0，那么这个数组最大的非空的子段和为数组中的最大值
        else a[i].ma2=a[i].ma;//否则，就是最大子段和
    }
    for (int i=1;i<=m;i++) cin>>b[i];
//  for (int i=1;i<=n;i++) cout<<"!! "<<a[i].lmax<<' '<<a[i].rmax<<' '<<a[i].sum<<' '<<a[i].ma<<endl<<"?? "<<a[i].lmax2<<" "<<a[i].rmax2<<" "<<a[i].ma2<<endl;
    build(1,1,m);//建线段树
    cout<<t[1].ma2;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while (t--) sol();
    return 0;
}