Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)-E. Let Them Slide
题意：n×w的方格中，每一行有cnti个数字，
每一行的数字都连续的放在一起，但是可以任意的平移。问每一列的最大和为多少。

单调栈+差分

能想到维护每个数字在该行能影响到哪些列，一开始想单调栈，但是不知道维护出来之后怎么累加的问题，
对于每行的第i+1列，其实和第i列有很大的关系，（由第i列加一些值减一些值得到）//差不多滑窗？？？
记录每个值影响区间的左右端点之后，左端点处就把该值加进来，右端点加一处就把该值影响减去，
最后对差分数组做一个前缀和求出原数组。
方案一：
对于每一行的第i个数字,记录左边第一个大于它的数字下标j,
右边第一个大于等于它的数字下标k.
这个数字可以贡献的区间范围受到了j和k的限制.
例如,如果某一个区域j可以移动到这,i也可以移动到这,那么肯定优先选j. 所以相当于i可以影响的范围缩小.
方案二虽然操作骚气但是空间和时间复杂度都很挫，，相比之下单调栈就优秀的多，其中的差分思想很重要
重点在i列与i+1列的关系：i+1列由i列加减一些值得到，所以维护一个sum[i+1]-sum[i]的数列，最后加和
int q,w,n;
int a[MAXN];
int l[MAXN],r[MAXN];
ll sum[MAXN];
void input()
{
    rd(q),rd(w);
    while(q--)
    {
        rd(n);
        for(int i=1;i<=n;++i) rd(a[i]);
        a[0]=a[n+1]=INF;//
        for(int i=1;i<=n;++i)
        {
            l[i]=i;
            while(a[l[i]-1]<a[i]) l[i]=l[l[i]-1];
        }
        for(int i=n;i>=1;--i)
        {
            r[i]=i;
            while(a[r[i]+1]<a[i]) r[i]=r[r[i]+1];
        }
        for(int i=1;i<=n;++i)
        {
            int ll=i,rr=i+w-n;
            if(l[i]!=1&&a[l[i]-1]>a[i]) ll=max(ll,w-n+l[i]);//如果左侧存在比他大的并且可以通过向右滑动到达这里，那么l<i
            if(r[i]!=n) rr=min(rr,r[i]);//因为一开始就是按照在滑块在最左侧来算的，右侧比他大的不可能到达这里，所以限制条件只有滑动范围
            if(a[i]<0) rr=min(n,rr),ll=max(ll,w-n+1);//如果小于零，还要看零能不能到达这里 
            if(rr<ll) continue;//对答案无贡献
            sum[ll]+=a[i];
            sum[rr+1]-=a[i];//差分
        }
    }
}
int main()
{
    input();
    for(int i=1;i<=w;++i)
    {
        sum[i]+=sum[i-1];
        printf("%lld ",sum[i]);
    }
    cout<<endll;
    //stop;
    return 0;
}

大概是模拟做法

对于第 i 行的第 j 个方块，如果这排方块的总长度为cnt，那么可以算出来该方块可以移动到[[j,w+j−cnt]列，
对于每一列（假设为 j ）我们可以使用两个vector分别记录第j列添加的元素(行，值)，开始移除的元素(行,值)。
那么我们就可以动态更新第 j 列每行的待选元素。
对每一行开一个multiset，然后按列从左枚举到右，multiset[i]维护第i行在当前列中有哪些数字是可以放的，那么我们取最大的那个就行。

自己的STL太菜了补一下📑

1，multiset，元素可重复有序集合，插入与删除都是logn（然鹅vector是n），不指定规则默认从小到大
2，rbegin()，返回end()前一个迭代器，也就是最后一个元素值
3，erase(it)，删除某元素或者某段，it为迭代器
int n,w;
ll ans[MAXN];
vector<pii >in[MAXN],out[MAXN];//维护每一列出进的值
multiset<ll>mx[MAXN];//对每一行维护最大值
void input()
{
    rd(n),rd(w);
    for(int i=1;i<=n;++i)
    {
        int len,l,r,d;rd(len);
        if(len<w)
        {
            l=1,r=w-len,d=0;
            in[l].push_back(make_pair(d,i));
            out[r].push_back(make_pair(d,i));
            l=len+1,r=w;
            in[l].push_back(make_pair(d,i));
            out[r].push_back(make_pair(d,i));
        }
        for(int j=1;j<=len;++j)
        {
            rd(d);l=j,r=j+w-len;
            in[l].push_back(make_pair(d,i));//在该位置进,第i行
            out[r].push_back(make_pair(d,i));//在该位置出
        }
    }
}
void solve()
{
    for(int i=1;i<=w;++i)//按行处理
    {
        for(int j=0;j<in[i].size();++j)
        {
            pii d=in[i][j];//要进入的元素//用second找到更新哪一行
            if(mx[d.second].begin()!=mx[d.second].end())
                ans[i]-=*mx[d.second].rbegin();//rbegin指向最后一个值
            mx[d.second].insert(d.first);
            ans[i]+=*mx[d.second].rbegin();
        }
        ans[i+1]=ans[i];//每个out的后一个位置才是数字无法达到的地方
        for(int j=0;j<out[i].size();++j)
        {
            pii d=out[i][j];//要删去的元素
            ans[i+1]-=*mx[d.second].rbegin();
            mx[d.second].erase(mx[d.second].find(d.first));
            if(mx[d.second].begin()!=mx[d.second].end())
                ans[i+1]+=*mx[d.second].rbegin();//
        }
    }
}
int main()
{
    input();
    solve();
    for(int i=1;i<=w;++i) printf("%lld ",ans[i]);
    cout<<endll;
    return 0;
}