CF 1795E Explosions?

有一個長度為 $n$ 的陣列 $h_i$，有如下兩個操作：

1. 任選一個 $i$，令 $h_i \gets h_i - 1$，代價為 $1$。
2. 任選一個 $i, x$，令 $h_i \gets h_i - x$，代價為 $x$。 如果操作 2 使得 $h_i = 0$ 了，那麼就會接著對相鄰的兩個 $h_{i-1}$ 和 $h_{i+1}$ 進行 $x = h_i - 1$ 的操作 2，如此遞迴下去。

只能使用一次操作 2，且操作 2 要能把所有非 0 的 $h$ 變成 0，問最小代價。

由於要一口氣使所有 $h_i$ 變成 0，則操作 2 之前必須用操作 1 把 $h$ 陣列變成單峰的，即存在一個 $i$ 使得 $h_0$ 到 $h_i$ 嚴格單調遞增，$h_i$ 到 $h_{n-1}$ 嚴格單調遞減。令 $pre_i$ 表示 $0$ 到 $i$ 單調遞增的代價，$back_i$ 表示 $i$ 到 $n-1$ 單調遞減的代價，則答案就是 $\min\{pre_i + back_i + h_i\}$。

$h_i$ 好求，$pre_i$ 和 $back_i$ 求法一致，所以只用考慮如何求 $pre_i$。

容易想到單調棧，我們用一個二元組 $(h, w)$ 來表示一個最高高度為 $h$、寬度為 $w$、相鄰兩數高差為 $1$ 的階梯。列舉 $i$，如果棧頂的 $h_{top}$ 大於 $h_i - w_i$，則不單調，需要累加答案，並彈出棧頂，並使 $w_i \gets w_i + w_top$。

struct node_t
{
    int h, w;
    node_t() {}
    node_t(int h, int w) : h(h), w(std::min(h, w)) {}
    long long maxsize(int h)
    {
        return (long long)h * (h + 1) / 2;
    }
    long long size()
    {
        if (h <= w) return maxsize(h);
        return maxsize(h) - maxsize(h - w);
    }
};
 
void solve()
{
    int n;
    cin >> n;
    vector<int> h(n);
    for (auto &i : h) cin >> i;
 
    auto calc_pre = [](const std::vector<int> &h) -> std::vector<long long>
    {
        int n = h.size();
        std::vector<long long> res(n);
        std::stack<node_t> s;
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            node_t cur(h[i], 1);
            while (!s.empty() && cur.h - cur.w < s.top().h) {
                node_t tmp = s.top();
                s.pop();
                node_t new_cur = node_t(cur.h, cur.w + tmp.w);
                ans += cur.size() + tmp.size() - new_cur.size();
                cur = new_cur;
            }
            s.emplace(cur);
            res[i] = ans;
        }
        return res;
    };
    auto pre = calc_pre(h);
    std::ranges::reverse(h);
    auto back = calc_pre(h);
    std::ranges::reverse(h);
    std::ranges::reverse(back);
    auto ans = std::numeric_limits<long long>::max();
    for (int i = 0; i < n; i++) {
        ans = std::min(ans, pre[i] + back[i] + h[i]);
    }
    cout << ans << endl;
}