CF2176E Remove at the lowest cost 题解

Mier_Samuelle · 2025-12-15 20:05:54 · 题解

对于每个位置 1 \le i \le n，我们记 l_i 为 i 左侧满足 a_{l_i}>a_i 的最后一个位置，r_i 为 i 右侧满足 a_{r_i}>a_i 的第一个位置。不难发现，[l_i,r_i] 为使用 i 能删除的极长区间，且删除该区间中每个元素所需花费的代价为 c_i。求 l_i,r_i 可以用单调栈做。

考虑求删除每个元素所需花费的最小代价。将 c_i 从大到小排序，依次将区间 [l_i,r_i] 赋值为 c_i，则结束时位置 i 上的所赋的值即为删除 i 所需花费的最小代价。至于修改操作，只需要将区间 [l_{p_i},r_{p_i}] 赋值为 0 即可。答案即为全局和减去全局最大值。线段树维护。

总复杂度 O(n \log n)。

:::success[代码]

#include <bits/stdc++.h>
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int a[MAXN], c[MAXN], st[MAXN], li[MAXN], ri[MAXN], id[MAXN], p[MAXN], tag[MAXN << 2], mx[MAXN << 2], len[MAXN << 2], n, top;
ll sum[MAXN << 2];
bool cmp(int x, int y){
    return c[x] > c[y];
}
void pushdown(int u){
    if (tag[u] == -1){
        return;
    }
    sum[ls] = 1ll * tag[u] * len[ls];
    sum[rs] = 1ll * tag[u] * len[rs];
    mx[ls] = mx[rs] = tag[u];
    tag[ls] = tag[rs] = tag[u];
    tag[u] = -1;
    return;
}
void pushup(int u){
    sum[u] = sum[ls] + sum[rs];
    mx[u] = max(mx[ls], mx[rs]);
    return;
}
void build(int u, int l, int r){
    len[u] = r - l + 1;
    tag[u] = mx[u] = -1;
    sum[u] = 0;
    if (l == r){
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    return;
}
void update(int u, int l, int r, int lq, int rq, int x){
    if (lq <= l && r <= rq){
        sum[u] = 1ll * x * len[u];
        mx[u] = x;
        tag[u] = x;
        return;
    }
    pushdown(u);
    if (lq <= mid){
        update(ls, l, mid, lq, rq, x);
    }
    if (rq > mid){
        update(rs, mid + 1, r, lq, rq, x);
    }
    pushup(u);
    return;
}
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> c[i];
    }
    top = 0, st[0] = 0;
    for (int i = 1; i <= n; i++){
        while (top && a[st[top]] <= a[i]){
            top--;
        }
        li[i] = st[top];
        st[++top] = i;
    }
    top = 0, st[0] = n + 1;
    for (int i = n; i >= 1; i--){
        while (top && a[st[top]] <= a[i]){
            top--;
        }
        ri[i] = st[top];
        st[++top] = i;
    }
    for (int i = 1; i <= n; i++){
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    build(1, 1, n);
    for (int i = 1; i <= n; i++){
        update(1, 1, n, li[id[i]] + 1, ri[id[i]] - 1, c[id[i]]);
    }
    cout << sum[1] - mx[1] << " ";
    for (int i = 1; i <= n; i++){
        cin >> p[i];
        update(1, 1, n, li[p[i]] + 1, ri[p[i]] - 1, 0);
        cout << sum[1] - mx[1] << " ";
    }
    cout << endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::