题意

有一个长度为 $n$ 的排列 $p_i$，你可以执行以下操作任意次：

• 将数字 $x$ 移动到任意一个位置，花费 $A_x$
• 将数字 $x$ 移动到开头，花费 $B_x$
• 将数字 $x$ 移动到结尾，花费 $C_x$

求排序最小代价。$n \leq 2 \times 10^5$。

题解

首先 $B_x,C_x$ 都要和 $A_x$ 取 $\min$。

手动模拟一下，我们先固定一些不动的数 $a_1,a_2,\ldots,a_m$，设 $i$ 的初始位置为 $ps_i$，那么一定要有 $ps_{a_1} < ps_{a_2} < \ldots < ps_{a_m}$。

这种情况下的代价，首先 $[1,a_1)$ 的所有数字都要用 $B_x$ 操作扔到前面，然后 $(a_m,n]$ 的数字都用 $C_x$ 的代价扔到后面。在 $(ps_{a_1},ps_{a_m})$ 的要动的数字都用 $A_x$ 的代价调整位置。

那么有可能所有位置都不动吗？显然不可能。因为有一个位置不动的时候，不会影响其他的位置的安排，并且还能少一个代价。所以至少有一个位置不动更优。

记 $s_i = \sum_{j=1}^i A_i,pre_i = \sum_{j=1}^i B_i,suf_i = \sum_{j=1}^n C_i$，这个就很向类似最长上升子序列的东西，可以dp。设 $f_i$ 表示钦定 $i$ 数字不动的答案，前 $i$ 个数字的代价和。转移：

• 这同时也是第一个不动的数字，$f_i = pre_{i-1}$
• 枚举前面一个不动的数字，$f_i = \min_{j < i,ps_j < ps_i} f_j + s_{i-1}-s_j$

第二种显然可以用树状数组优化，复杂度 $O(n \log n)$。

代码

所有人的代码写的都差不多，我放个我的树状数组版本：

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

inline char nc(){
    #define SIZE 1000003
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
}

inline void read(int &x){
    x = 0;char ch = nc();bool flag = 0;
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1)+(x<<3)+(ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

const int MAXN = 2e5 + 5;
int n,p[MAXN],a[MAXN],b[MAXN],c[MAXN];
int ps[MAXN];
LL f[MAXN],sm[MAXN],pre[MAXN],suf[MAXN];

struct BIT{
    LL tree[MAXN];
    #define lowbit(x) ((x)&(-(x)))
    BIT(){CLR(tree,0x3f);}

    inline void add(int p,LL x){
        for(;p < MAXN;p += lowbit(p)) tree[p] = std::min(tree[p],x);
    }

    inline LL query(int p){
        LL res = 1e18;
        for(;p;p -= lowbit(p)) res = std::min(res,tree[p]);
        return res;
    }
}bit;

int main(){
    read(n);
    FOR(i,1,n) read(p[i]),ps[p[i]] = i;
    FOR(i,1,n) read(a[i]),read(b[i]),read(c[i]),b[i] = std::min(b[i],a[i]),c[i] = std::min(c[i],a[i]);
    FOR(i,1,n) pre[i] = pre[i-1]+b[i];
    ROF(i,n,1) suf[i] = suf[i+1]+c[i];
    FOR(i,1,n) sm[i] = sm[i-1]+a[i];
    f[0] = 0;
    LL ans = 1e18;
    FOR(i,1,n){
        f[i] = pre[i-1];
        f[i] = std::min(f[i],sm[i-1]+bit.query(ps[i]-1));
        bit.add(ps[i],f[i]-sm[i]);
        ans = std::min(ans,f[i]+suf[i+1]);
    }
    printf("%lld\n",ans);
    return 0;
}