题解：CF2176E Remove at the lowest cost

AxDea · 2025-12-13 08:12:27 · 题解

CF2176E - Remove at the lowest cost

大致写一下思考过程：

• 首先自然的想到从 c_i 最小的位置开始，删除周边 \neq i 的位置 j，且 a_j \le a_i。
• 然后发现删除的位置是有范围的，不难得出，若范围为 [l_i, r_i]，那么 a_{l_i - 1} > a_i, a_{r_i + 1} > a_i, \max\limits_{l_i\le k\le r_i} a_k \le a_i，且删除掉这个区间的每个元素的每次花费为 c_i，这个 l_i 和 r_i 是容易求的。
• 先考虑第一个答案是多少，由上面可得，一段区间内所有花费都是一样的，所以可以考虑线段树的区间染色操作（即把数组中位置属于区间 [l_i, r_i] 的所有元素赋值为 c_i）。
• 那么一种最优的染色方案就是按照 c_i 从大到小排序，按照顺序将 [l_i, r_i] 上的元素染成 c_i。
• 然后考虑删掉一个元素的要求，可以发现答案就是整个数组的和 \text{sum} 直接减去数组中最大的元素 \text{mx}。
• 这个时候你可能有很多问号，所以接下来要来证明正确性。
• 答案的统计方式是没有问题的，有问题的是假如一段区间 [l_p, r_p] 先赋上了值 c_p，然后又有一个区间 [l_q, r_q] 之后赋上了值 c_q，且 l_p < l_q, r_q < r_p, c_p > c_q。那么 c_p 这个值真的能表示修改 [l_p,l_q - 1] 和 [r_q + 1, r_p] 中的元素代价吗？
• 答案是，这就是对的，不难发现 a_p > a_q，所以 p \not \in [l_q, r_q]，所以存在一种删除方案满足经过染色的代价数组的结果（即先用 q 把 [l_q, r_q] 删完，然后再用 p 开始删除 [l_p, r_p] 的剩余部分）。
• 最后就简单了，由于新加入的点 p_i 对应的 c = 0，所以可以跟在上面的最优染色方案后面，直接把区间 [l_{p_i}, r_{p_i}] 的所有值改为 0 即可。

时间复杂度 \mathcal O (n\log n)。

int rt, sl, L[N << 1], R[N << 1]; ll val[N << 1], mx[N << 1], tag[N << 1], len[N << 1];
int n, a[N], id[N]; ll c[N];
inline void up(int p) { val[p] = val[L[p]] + val[R[p]], mx[p] = max(mx[L[p]], mx[R[p]]); }
inline void opt(int p, ll k) { val[p] = len[p] * k, mx[p] = k, tag[p] = k; }
inline void down(int p) { (tag[p] != -1) && (opt(L[p], tag[p]), opt(R[p], tag[p]), tag[p] = -1); }
void Bld(int& p, int l, int r) {
    p = ++sl, len[p] = r - l + 1, tag[p] = -1;
    if (l == r) return val[p] = mx[p] = 1e13, void();
    int mid = l+r >> 1;
    Bld(L[p], l, mid), Bld(R[p], mid + 1, r);
    up(p);
}
void upd(int p, int l, int r, int nl, int nr, ll k) {
    if (l == nl && nr == r) return opt(p, k);
    down(p);
    int mid = nl+nr >> 1;
    if (r <= mid) upd(L[p], l, r, nl, mid, k);
    else if (l > mid) upd(R[p], l, r, mid + 1, nr, k);
    else upd(L[p], l, mid, nl, mid, k), upd(R[p], mid + 1, r, mid + 1, nr, k);
    up(p);
}
inline void clear() {
    forn (i, 1, sl) L[i] = R[i] = 0, val[i] = mx[i] = len[i] = 0, tag[i] = -1;
    rt = sl = 0;
}
int stk[N], top, lp[N], rp[N];
inline void solve() {
    cin >> n;
    forn (i, 1, n) cin >> a[i];
    forn (i, 1, n) cin >> c[i], id[i] = i;
    sort (id + 1, id + n + 1, [&] (int x, int y) {
        return c[x] > c[y];
    });
    stk[0] = 0, top = 0;
    forn (i, 1, n) {
        while (top && a[stk[top]] <= a[i])
            top -- ;
        lp[i] = stk[top];
        stk[++top] = i;
    }
    stk[0] = n + 1, top = 0;
    form (i, n, 1) {
        while (top && a[stk[top]] <= a[i])
            top -- ;
        rp[i] = stk[top];
        stk[++top] = i;
    }
    Bld(rt, 1, n);
    forn (i, 1, n) upd(rt, lp[id[i]] + 1, rp[id[i]] - 1, 1, n, c[id[i]]);
    cout << val[rt] - mx[rt] << ' ';
    forn (i, 1, n) {
        int u;
        cin >> u;
        upd(rt, lp[u] + 1, rp[u] - 1, 1, n, 0);
        cout << val[rt] - mx[rt] << " \n"[i == n];
    }
 }