题意
给你一个长度为 $N$ 的打乱的排列 $P$，每个数字移动的代价为：
- $A_i$, 向任意位置移动
- $B_i$, 移动到最左边
- $C_i$, 移动到最右边
求恢复成升序需要付出的最小代价。
题解
每个数字，只可能付出 $0/A_i/B_i/C_i$ 的代价，因此最终的方案一定是分为了三段。第一段全付出了B的代价，第二段中有位置刚好的，或需要付出A来调整的，第三段全付出了C的代价。
所以我们可以令 $dp_i$ 表示第二段在 $i$ 前一位结束的最小代价，可以写出以下式子：
\[dp_i = min(preB_{i-1}, min_{j=1}^{pos_i-1}(dp_j+preA_{i-1}-preA_{j}))\]解读一下，就是我们可以选择全选B，也可以找到之前的一个位置，保持它的位置不变，再让这中间全选A
那么最终答案即可表示为：
\[ans = min_{i=1}^N(dp_i+preC_N-preC_i)\]其中 $dp$，可抽离出与 $j$ 相关的东西放到树状数组维护，做到 $\Theta(n log n)$
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int p[202020],where[202020],a[202020],b[202020],c[202020];
ll prea[202020],preb[202020],prec[202020];
int n;
ll dp[202020];
ll C[202020];
#define lb(x)(x&-x)
inline void modify(int p,ll x){for(;p<=n;p+=lb(p))C[p]=min(C[p],x);}
inline ll qry(int p){ll res=0x3f3f3f3f3f3f3f3f;for(;p;p-=lb(p))res=min(res,C[p]);return res;}
int main(){
memset(C,0x3f,sizeof C);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&p[i]),where[p[i]]=i;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
b[i]=min(b[i],a[i]);
c[i]=min(c[i],a[i]);
prea[i]=prea[i-1]+a[i];
preb[i]=preb[i-1]+b[i];
prec[i]=prec[i-1]+c[i];
}
ll ans=LONG_LONG_MAX;
for(int i=1;i<=n;++i){
dp[i]=min(preb[i-1],qry(where[i])+prea[i-1]);
ans=min(ans,dp[i]+prec[n]-prec[i]);
modify(where[i],dp[i]-prea[i]);
}
printf("%lld\n",ans);
}