题解：CF75D Big Maximum Sum

#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;
}