题目大意
给你n个序列,每个一行
每个序列是可以左右移动的
对于每一列问在随意左右移动这些序列的情况下
这一列的每个数的和最大是多少
分析
对于每个序列分为两种情况
[1]长度小于长度的一半
我们发现这种情况下一定是两头长度为k的地方只能考虑序列开头/结尾的前k个
于是我们直接维护开头和结尾前k个的最大值
对于每一个最大值的影响区间我们差分处理
[2]长度大于等于长度的一半
对于全长的每一个点我们可以轻松算出它对应序列上的哪些点
直接st表求最大值即可
仍然使用差分的方式维护
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack> using namespace std; #define li long long int n,w,m,lg[1000100],st[2000100][23]; li ans[1000100]; inline int q(int le,int ri){ int k=lg[ri-le+1]; return max(st[le][k],st[ri-(1<<k)+1][k]); } int main(){ int i,j,k; scanf("%d%d",&n,&w); for(i=2;i<=1000000;i++)lg[i]=lg[i>>1]+1; for(int _=1;_<=n;_++){ scanf("%d",&m); for(i=1;i<=m;i++)scanf("%d",&st[i][0]); for(i=1;i<=20;i++) for(j=1;j<=m;j++) st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]); if(2*m>=w){ for(i=1;i<=w;i++){ int le=m-w+i,ri=i,v=q(max(le,1),min(ri,m)); if(le<1||ri>m)v=max(v,0); ans[i]+=(li)v; ans[i+1]-=(li)v; } }else { int v1=0,v2=0; for(i=1;i<=m;i++){ v1=max(v1,st[i][0]); v2=max(v2,st[m-i+1][0]); ans[i]+=(li)v1; ans[i+1]-=(li)v1; ans[w-i+1]+=(li)v2; ans[w-i+2]-=(li)v2; } ans[m+1]+=(li)v1; ans[w-m+1]-=(li)v1; } } for(i=1;i<=w;i++){ ans[i]+=ans[i-1]; printf("%lld ",ans[i]); } puts(""); return 0; }