由于每个数组可以滑动。
我们对于一个位置，要考虑它是否可以为空，能放的最大值是多少。
每行的每个位置都直接这样做显然会TLE。
我们发现每行可以分为三个部分（有些时候不可以，随便讨论一下啦）
第一个部分是只能放前几个。
第二个部分是所有的都可以放。
第三个部分是只能放后几个。
然后我们发现第二个部分都是一样的，直接线段树区间处理就行了
第一个部分和第三个部分只能暴力，但是发现这两个部分最多为\(2*l_i\)。
所以总时间复杂度为\(O(\sum_{i=1}^{n}l_i\log m)\)
代码：
#include#include #include #include using namespace std;#define rg registervoid read(int &x){ char ch;bool ok; for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1; for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=1e6+10;int n,m,mx[maxn*4];void build(int x,int l,int r){ mx[x]=-2e9;if(l==r)return ; int mid=(l+r)>>1; build(x<<1,l,mid),build(x<<1|1,mid+1,r);}void update(int x){mx[x]=max(mx[x<<1],mx[x<<1|1]);}void change(int x,int l,int r,int a,int c){ if(l==r)return mx[x]=max(mx[x],c),void(); int mid=(l+r)>>1; if(a<=mid)change(x<<1,l,mid,a,c); else change(x<<1|1,mid+1,r,a,c); update(x);}int get(int x,int l,int r,int a,int b){ if(a<=l&&b>=r)return mx[x]; int mid=(l+r)>>1,ans=-2e9; if(a<=mid)ans=max(ans,get(x<<1,l,mid,a,b)); if(b>mid)ans=max(ans,get(x<<1|1,mid+1,r,a,b)); return ans;}struct segment_tree{ long long ans[maxn*4],la[maxn*4]; void update(int x){ans[x]=max(ans[x<<1],ans[x<<1|1]);} void pushdown(int x){ ans[x<<1]+=la[x],ans[x<<1|1]+=la[x]; la[x<<1]+=la[x],la[x<<1|1]+=la[x]; la[x]=0; } void change(int x,int l,int r,int a,int b,int c){ if(a<=l&&b>=r)return ans[x]+=c,la[x]+=c,void(); int mid=(l+r)>>1;if(la[x])pushdown(x); if(a<=mid)change(x<<1,l,mid,a,b,c); if(b>mid)change(x<<1|1,mid+1,r,a,b,c); update(x); } long long get(int x,int l,int r,int a){ if(l==r)return ans[x]; int mid=(l+r)>>1;if(la[x])pushdown(x); if(a<=mid)return get(x<<1,l,mid,a); else return get(x<<1|1,mid+1,r,a); }}T;signed main(){ read(n),read(m); for(rg int i=1,w;i<=n;i++){ read(w);build(1,1,w); for(rg int j=1,x;j<=w;j++)read(x),change(1,1,w,j,x); int now=get(1,1,w,1,w),l=w+1,r=m-w; if(w+1<=m-w)now=max(now,0),T.change(1,1,m,w+1,m-w,now); else if(w>=m-w+1){ l=m-w+1,r=w; for(rg int j=l;j<=r;j++){ now=get(1,1,w,j-m+w,j); T.change(1,1,m,j,j,now); } } for(rg int j=1;j