Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) E.Let them slide(单调队列)

题目链接
大意：给你一个n*m的空间，每行都有一些元素，你可以整体滑动这些元素，让你求出每列和的最大值
思路：如果行的元素不能充满m列的话，我们在前后补上0，防止负数。然后扫一遍记录每个元素可能出现的列号，然后维护一个单调不增的单调队列，每次弹出元素就在差分数组中更新答案，然后把这个值存到队列中，要注意的是我们每次弹出的元素，要更新答案的时候，他作为最大值代表的区间是可以计算的，如果这个区间不合法就不用更新了。
然后扫完把队列中剩余的元素再更新一遍答案就好了。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e6 + 11;
int n, w;
int a[N], b[N], l[N], r[N];
LL ans[N];
struct uzi {
    int l, r, pos;
} q[N];
void pu(int a, int c, int d, int sta) {
    //cout << "NEW-->" << a << ' ' << c << ' ' << d << ' ' << sta << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        int Q;
        cin >> Q;
        int h = 1, o = 0;
        if (Q < w) {//补零
            b[1] = 0;
            b[Q + 2] = 0;
            for (int j = 2; j <= Q + 1; j++)cin >> b[j];
            for (int j = 1; j <= Q + 2; j++)l[j] = j - 1, r[j] = j - 1 + w - Q;
            Q += 2;
        } else {
            for (int j = 1; j <= Q ; j++)cin >> b[j];
            for (int j = 1; j <= Q ; j++)l[j] = j , r[j] = j  + w - Q;
        }
        for (int j = 1; j <= Q; j++) {
            while (h <= o && b[q[o].pos] < b[j] && l[j] <= r[q[o].pos]) {//维护一个单调递减的单调队列，如果区间互不影响就不用弹出
                if (min(q[o].r + 1, l[j]) < q[o].l) {//区间不合法的情况
                    --o;
                    continue;
                }
                ans[q[o].l] += b[q[o].pos];
                ans[min(q[o].r + 1, l[j])] -= b[q[o].pos];//更新的右端点必然是不能超过新加入的左端点啦
                o--;
            }
            if (h > o)q[++o] = {l[j], r[j], j}, pu(l[j], r[j], j, 1);
            else q[++o] = {max(q[o - 1].r + 1, l[j]), r[j], j}, pu(max(q[o - 1 ].r + 1, l[j]), r[j], j, 2);
        }
        while (h <= o) {//更新剩余的即可
            ans[q[h].l] += b[q[h].pos];
            ans[q[h].r + 1] -= b[q[h].pos];
            h++;
        }
    }
    for (int i = 1; i <= w; i++) cout << (ans[i] += ans[i - 1]) << ' ';
    return 0;
}