CodeForces 1295E Permutation Separation

题意

给定一个排列$p$，和一数组$a$，任意取一数$k$（$1\leq k<n$），将排列分为两个序列$p_1$,$p_2$,…,$p_k$和$p_{k+1}$,$p_{k+2}$,…,$p_{n}$，然后将两个序列中的某些数移到另一个序列，使得第一个序列中的数小于第二个序列中的所有数（任意一个序列为空也可），移动$p[i]$的花费为$a[i]$，问最小花费

分析

设$j$为操作完后左半序列的元素个数，易知左半部分的数为$1$-$j$，右半部分的数为$j+1$-$n$。

对于一个数$p[i]$，如果将其分在左半边，则

若$j>=p[i]$，则花费不变
若$j<p[i]$，则花费需加上$a[i]$

因此先假设所有的元素都在右半部分，枚举$1$-$n-1$，枚举$k$，每次更新$p[k]$的贡献，由上述可知$p[k]$对$[1,p[i]-1]$贡献为$a[i]$，而因为一开始所有元素都在右半部分，所以对$[p[i],n]$的贡献为$-a[i]$，每次用线段树全局最小值更新答案

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
const int maxn = (ll) 2e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
int t[maxn << 2], tag[maxn << 2];

void push_down(int st) {
    if (!tag[st])
        return;
    t[ls] += tag[st];
    t[rs] += tag[st];
    tag[ls] += tag[st];
    tag[rs] += tag[st];
    tag[st] = 0;
}

void update(int st, int l, int r, int x, int y, int val) {
    if (l >= x && r <= y) {
        t[st] += val;
        tag[st] += val;
        return;
    }
    push_down(st);
    int mid = (l + r) >> 1;
    if (x <= mid)
        update(ls, l, mid, x, y, val);
    if (y > mid)
        update(rs, mid + 1, r, x, y, val);
    t[st] = min(t[ls], t[rs]);
}

int a[maxn], p[maxn];

void solve() {
    int n;
    cin >> n;
    rep(i, 1, n)cin >> p[i];
    rep(i, 1, n)cin >> a[i];
    rep(i, 1, n)update(1, 1, n, p[i], n, a[i]);
    int ans = min(a[1], a[n]);
    rep(i, 1, n - 1) {
        update(1, 1, n, p[i], n, -a[i]);
        if (p[i] != 1)
            update(1, 1, n, 1, p[i] - 1, a[i]);
        ans = min(ans, t[1]);
    }
    cout << ans;
}

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