CF1208E 一种单调栈做法

· · 题解

本题的所有题解似乎都是单调队列和线段树，然而它其实也可以是一道思维量与细节都很高的单调栈好题。
根据题意，数组不能平移到方框之外，所以对于每个数组的每一个元素，它能够做出贡献的范围是一个区间。如果我们用 i 表示方框中位置的横坐标，用 x 表示元素在数组中的坐标，我们可以推出如果 x 对 i 处的答案有贡献 i \in [x,x+w-l]。然而对于同一个位置，每一个数组中只能有一个元素做出贡献。所以我们可以用单调栈扫两次，把较小元素的区间中，和较大元素区间重合的部分去掉。核心代码如下：

for (int x = 1; x <= len; ++x) {
            r[x] = x + w - len;
            while (top && v[s[top]] <= v[x]) {
                r[s[top]] = min(r[s[top]], x - 1);
                --top;
            }
            s[++top] = x;
        }
        top = 0;
        for (int x = len; x; --x) {
            l[x] = x;
            while (top && v[s[top]] < v[x]) {
                l[s[top]] = max(l[s[top]], x + w - len + 1);
                --top;
            }
            s[++top] = x;
        }
        top = 0;

具体原理就是在单调栈中维护一个严格不递增的序列，在每个元素入栈时把它的左端点设为 x 在每个元素入栈时把所有小于它的元素全部出栈，并尝试用右端点限制左端点，因为比它小的元素右端点只能到比它左端点小 1 的位置，再往右就会与它的区间重合。对于求右端点方法也是一样的，只要把循环倒过来即可。注意 l 对应代码中的 len，代码中的 l 代表右端点。在每一轮以后，我们要用每个元素贡献答案中的区间，使用差分维护每次更新即可做到 \mathcal{O}(1) 最后总时间复杂度是 \mathcal{O}(\sum{l}+n)。此外，还有两点应当注意，首先数组中小于零的值是不能更新答案中 [w-l,l] 以外的部分（因为这部分以外的答案可以不被数组的任何一部分覆盖，相当于取 0，优于负数），其次为了保证区间不重合也不缺少，单调栈的出栈判定必须是一个取等，另一个不取。最后代码如下：

// 万能头与IO略（本题输入很大，建议采用快读）
namespace Solution {
constexpr int max_w = 1e6 + 10;
int l[max_w], r[max_w], v[max_w]; // 每个元素的大小于区间
int s[max_w], top = 0; // 手写栈
ll d[max_w]; // 答案的差分数组
void solve() {
    int n, w;
    IO::io.read(n);
    IO::io.read(w);
    for (int i = 1; i <= n; ++i) {
        int len;
        IO::io.read(len);
        for (int i = 1; i <= len; ++i) IO::io.read(v[i]);
        for (int i = 1; i <= len; ++i) {
            r[i] = i + w - len;
            while (top && v[s[top]] <= v[i]) {
                r[s[top]] = min(r[s[top]], i - 1); // 小于等于当前元素的元素贡献的区间最右到 i-1（这里的i其实是x但是懒得改了）
                --top;
            }
            s[++top] = i;
        }
        top = 0;
        for (int i = len; i; --i) {
            l[i] = i;
            while (top && v[s[top]] < v[i]) {
                l[s[top]] = max(l[s[top]], i + w - len + 1);
                --top;
            }
            s[++top] = i;
        }
        top = 0;
        // 数组一定会覆盖的区域，超出的部分负数的贡献无效
        int ml = w - len + 1, mr = len;
        for (int i = 1; i <= len; ++i) {
            if (v[i] < 0) l[i] = max(l[i], ml), r[i] = min(r[i], mr);
            if (l[i] > r[i]) continue;
            d[l[i]] += v[i];
            d[r[i] + 1] -= v[i];
        }
    }
    ll sum = 0;
    for (int i = 1; i <= w; ++i) {
        sum += d[i];
        IO::io.write(sum);
        IO::io.push(' ');
    }
    IO::io.push('\n');
}
}

int main() {
    Solution::solve();
    return 0;
}