\(\mathcal{Description}\)
??Link.
??有 \(n\) 个编号 \(1\sim n\) 的格子排成一排，并有三个权值序列 \(\{a_n\},\{h_n\},\{p_n\}\)，其中 \(\{p_n\}\) 是一个排列。从 \(i\) 跳到 \(j\)，必须满足 \(i<j\land p_i<p_j\)，代价为 \((h_i-h_j)^2+a_j\)，求从 \(1\) 跳到 \(n\) 的最小代价。
??\(n,h_i\le6\times10^5\)。
\(\mathcal{Solution}\)
??不就是个板子套板子吗你还水题解。
??设 \(f(i)\) 表示从 \(1\) 跳到 \(i\) 的最小代价，显然
\[\begin{aligned}f(i) &= \min_{j<i,p_j<p_i}\{f(j)+a_i+(h_i-h_j)^2\}\\&= a_i+h_i^2+\min_{j<i,p_j<p_i}\{f(j)+h_j^2-2h_ih_j\}.\end{aligned}
\]
转移条件是二维偏序关系，反手一个 CDQ，转移最优化的是一次函数，再丢一个李超树，复杂度 \(\mathcal O(n\log n\log h)\)。
??比树套树好写不知道多少，而且跑得飞快。
\(\mathcal{Code}\)
/*~Rainybunny~*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && ( q = buf + fread( p = buf, 1, 1 << 17, stdin ), p == q )
? EOF : *p++;
}
inline int rint() {
int x = 0, f = 1, s = fgc();
for ( ; s < ‘0‘ || ‘9‘ < s; s = fgc() ) f = s == ‘-‘ ? -f : f;
for ( ; ‘0‘ <= s && s <= ‘9‘; s = fgc() ) x = x * 10 + ( s ^ ‘0‘ );
return x * f;
}
typedef long long LL;
inline void chkmin( LL& a, const LL b ) { b < a && ( a = b ); }
const int MAXN = 6e5;
const LL LINF = 1ll << 60;
int n, mxh, h[MAXN + 5], p[MAXN + 5], a[MAXN + 5];
LL f[MAXN + 5];
std::vector<int> ord[MAXN * 2 + 5];
struct Line {
LL k, b;
inline LL operator () ( const int x ) { return k * x + b; }
};
struct SegmentTree {
Line line[MAXN + 5];
int lcnt, vers, ver[MAXN << 2], idx[MAXN << 2];
inline void clear() { lcnt = 0, ++vers; }
inline void insert( const int u, const int l, const int r, int id ) {
if ( ver[u] != vers ) return idx[u] = id, ver[u] = vers, void();
int mid = l + r >> 1;
if ( line[idx[u]]( mid ) > line[id]( mid ) ) std::swap( idx[u], id );
if ( l == r ) return ;
if ( line[idx[u]]( l ) > line[id]( l ) ) {
insert( u << 1, l, mid, id );
} else if ( line[idx[u]]( r ) > line[id]( r ) ) {
insert( u << 1 | 1, mid + 1, r, id );
}
}
inline void insert( const Line& l ) {
line[++lcnt] = l, insert( 1, 1, mxh, lcnt );
}
inline LL query( const int u, const int l, const int r, const int x ) {
if ( ver[u] != vers ) return LINF;
LL ret = line[idx[u]]( x );
if ( l == r ) return ret;
int mid = l + r >> 1;
if ( x <= mid ) chkmin( ret, query( u << 1, l, mid, x ) );
else chkmin( ret, query( u << 1 | 1, mid + 1, r, x ) );
return ret;
}
} sgt;
#define id( l, r ) ( ( l + r ) | ( l != r ) )
inline void build( const int l, const int r ) {
int u = id( l, r ); ord[u].resize( r - l + 1 );
if ( l == r ) return void( ord[u][0] = l );
int mid = l + r >> 1, lc = id( l, mid ), rc = id( mid + 1, r );
build( l, mid ), build( mid + 1, r );
std::merge( ord[lc].begin(), ord[lc].end(), ord[rc].begin(), ord[rc].end(),
ord[u].begin(), []( const int x, const int y ) { return p[x] < p[y]; } );
}
inline void solve( const int l, const int r ) {
if ( l == r ) return ;
int mid = l + r >> 1;
solve( l, mid ), sgt.clear();
for ( int u: ord[id( l, r )] ) {
if ( u <= mid && f[u] != LINF ) {
sgt.insert( { -2ll * h[u], 1ll * h[u] * h[u] + f[u] } );
} else if ( u > mid ) {
chkmin( f[u], 1ll * h[u] * h[u] + a[u]
+ sgt.query( 1, 1, mxh, h[u] ) );
}
}
solve( mid + 1, r );
}
#undef id
int main() {
n = rint();
rep ( i, 1, n ) p[i] = rint();
rep ( i, 1, n ) a[i] = rint();
rep ( i, 1, n ) h[i] = rint(), mxh = std::max( mxh, h[i] );
f[1] = a[1];
rep ( i, 2, n ) f[i] = LINF;
build( 1, n ), solve( 1, n );
printf( "%lld\n", f[n] );
return 0;
}