题解：CF1988E Range Minimum Sum

· · 题解

跟 CF1913F 很像，但是简单的多。

  • 给定长度为 n 的序列 a。求出对于每个 i = (1, 2, \dots, n)，序列 b = [a_1, a_2, \dots, a_{i - 1}, a_{i + 1} ,a_{i +2}, \dots, n] 的价值。
  • 序列 c 的价值为 \sum_{l=1}^{|c|} \sum_{r=l}^{|c|} \min _{l \le i \le r} c_i。

若没有删除操作，而是直接求原序列 a 的价值。那么有很经典的单调栈做法。求出 i 之前第一个 < a_i 的位置 l_i，或不存在为 0。以及 i 之后第一个 < a_i 的位置 r_i，或不存在为 n + 1。

只要 l \in [l_i + 1, i], r \in [i, r_i-1]，那么 \min_{j=l}^r a_j = a_i。因此答案为 \sum a_i \times (i-l_i) \times (r_i - i)。

仍然考虑这种拆贡献的做法。我们令 f(i) 表示将 a_i 删除后的答案。枚举 j 考虑 a_j 对哪些 f(i) 有贡献。

分类讨论：

除了 i = l_j 和 i = r_j 的情况外，都可以直接差分完成。对于这两种需要重新计算 l_j, r_j 的情况可以二分 + RMQ 计算。

// Problem: Range Minimum Sum
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1988E
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long ll;

#define int ll

int T, n, a[N];
int st[N][20];
int L[N], R[N];
int f[N];
int f_sum[N];       // f 的差分数组，用于区间加

void add(int l, int r, int d) {
    if (l <= r) f_sum[l] += d, f_sum[r + 1] -= d;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        st[i][0] = a[i];
        f[i] = f_sum[i] = 0;
    }

    for (int j = 1; j < 20; ++ j )
        for (int i = 1; i + (1 << j - 1) <= n; ++ i )
            st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

    auto RMQ = [&](int l, int r) {
        int k = log2(r - l + 1);
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    };

    stack<int> stk;
    for (int i = 1; i <= n; ++ i ) {
        while (stk.size() && a[stk.top()] > a[i]) stk.pop();
        L[i] = stk.size() ? stk.top() : 0;
        stk.push(i);
    }

    while (stk.size()) stk.pop();

    for (int i = n; i; -- i ) {
        while (stk.size() && a[stk.top()] > a[i]) stk.pop();
        R[i] = stk.size() ? stk.top() : n + 1;
        stk.push(i);
    }

    for (int j = 1; j <= n; ++ j ) {
        // 删除 a[j] 后，哪些 f(i) 会收到影响？
        add(1, L[j] - 1, a[j] * (j - L[j]) * (R[j] - j));
        add(R[j] + 1, n, a[j] * (j - L[j]) * (R[j] - j));
        add(L[j] + 1, j - 1, a[j] * (j - 1 - L[j]) * (R[j] - j));
        add(j + 1, R[j] - 1, a[j] * (j - L[j]) * (R[j] - 1 - j));
    }

    for (int i = 1; i <= n; ++ i ) f[i] = (f_sum[i] += f_sum[i - 1]);

    for (int i = 1; i <= n; ++ i ) {
        // 将 L[i] 删除
        int l = 1, r = L[i] - 1, res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (RMQ(mid, L[i] - 1) > a[i]) res = L[i] - mid, r = mid - 1;
            else l = mid + 1;
        }
        res += i - L[i];
        f[L[i]] += a[i] * res * (R[i] - i);
    }

    for (int i = 1; i <= n; ++ i ) {
        // 将 R[i] 删除
        int l = R[i] + 1, r = n, res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (RMQ(R[i] + 1, mid) > a[i]) res = mid - R[i], l = mid + 1;
            else r = mid - 1;
        }
        res += R[i] - i;
        f[R[i]] += a[i] * (i - L[i]) * res;
    }

    for (int i = 1; i <= n; ++ i ) cout << f[i] << ' ';
    cout << '\n';
    return;
}

signed main() {
    cin >> T;
    while (T -- ) solve();
    return 0;
}