题目链接：Codeforces - Let Them Slide
因为序列的长度之和小于1e6.所以我们只要对每一次操作是O(长度)那么就是ok的。
若：l*2<=w
那么有很多区间的位置都是全部能贡献的，所以左右端点区间暴力更新，中间的直接用最大值更新。
否则：
枚举总区间的每个位置。看能贡献的地方，然后区间max。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int sum[N],m,n,mx[N<<2],l,a[N];
void add(int l,int r,int x){sum[l]+=x,sum[r+1]-=x;}
#define mid (l+r>>1)
void build(int p,int l,int r){if(l==r){mx[p]=a[l]; return ;}build(p<<1,l,mid),build(p<<1|1,mid+1,r);mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
int ask(int p,int l,int r,int ql,int qr){if(l==ql&&r==qr) return mx[p];if(qr<=mid) return ask(p<<1,l,mid,ql,qr);else if(ql>mid) return ask(p<<1|1,mid+1,r,ql,qr);else return max(ask(p<<1,l,mid,ql,mid),ask(p<<1|1,mid+1,r,mid+1,qr));
}
signed main(){cin>>m>>n;for(int i=1;i<=m;i++){scanf("%lld",&l);for(int j=1;j<=l;j++) scanf("%lld",&a[j]);if(l*2<=n){int mx=0;for(int j=1;j<=l;j++) mx=max(mx,a[j]),add(j,j,mx); mx=0;for(int j=l;j>=1;j--) mx=max(mx,a[j]),add(n-l+j,n-l+j,mx);if(l*2<n) add(l+1,n-l,mx);}else{a[l+1]=0; build(1,0,l+1);for(int j=1;j<=n;j++) add(j,j,ask(1,0,l+1,max(0LL,j-n+l),min(j,l+1)));}}for(int i=1;i<=n;i++) sum[i]+=sum[i-1],printf("%lld ",sum[i]);return 0;
}