当牛做吗网站源代码分享百度云,企业网站搭建流程,西安短视频制作公司,静态网站优化https://www.luogu.com.cn/problem/P4655
这东西长得就很像斜率优化的东西#xff0c;但是不能用朴素斜率优化#xff0c;因为横坐标不满足递增。
但我们可以直接用李超线段树维护即可。
#includebits/stdc.h
using namespace std;
#ifdef LOCAL#define debug(...…https://www.luogu.com.cn/problem/P4655
这东西长得就很像斜率优化的东西但是不能用朴素斜率优化因为横坐标不满足递增。
但我们可以直接用李超线段树维护即可。
#includebits/stdc.h
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else#define debug(...) void(0)
#endif
#define int long long
inline int read(){int x0,f1;char chgetchar();
while(ch0||ch9){if(ch-)f-1;
chgetchar();}while(ch0ch9){x(x1)
(x3)(ch^48);chgetchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000010
int n, m, i, j, k, T;
int h[N], c[N], s[N], f[N], rt; struct Lichao_tree {int tot, ls[N2], rs[N2]; pairint, inte[N2]; void build(int k, int l, int r) {if(!k) ktot, e[k]{0, 1e17}; if(lr) return ;int mid(lr)1; build(ls[k], l, mid); build(rs[k], mid1, r); }int calc(pairint, intp, int x) {return x * p.fi p.se; }void add(int k, int l, int r, pairint, intp) {if(lr) return e[k]p, /*debug(y %dx %d\n, p.fi, p.se), */void(); int mid(lr)1, s1, t1, sl, tl, sr, tr; s1calc(e[k], mid); t1calc(p, mid);debug([%lld %lld][%lld %lld]\n, e[k].fi, e[k].se, p.fi, p.se); if(t1 s1) swap(e[k], p); //, debug(swap Success !(%d %d) newp : [%d %d]\n, t1, s1, p.fi, p.se); slcalc(e[k], l); tlcalc(p, l);srcalc(e[k], r); trcalc(p, r);if(tl sl) add(ls[k], l, mid, p); if(tr sr) add(rs[k], mid1, r, p); }int que(int k, int l, int r, int x) {if(lr) return calc(e[k], x); int mid(lr)1, anscalc(e[k], x);
// debug(%lld %lld * %lld %lld\n, ans, e[k].fi, x, e[k].se); if(xmid) ansmin(ans, que(ls[k], l, mid, x)); else ansmin(ans, que(rs[k], mid1, r, x)); return ans; }
}Seg;signed main()
{#ifdef LOCALfreopen(in.txt, r, stdin);freopen(out.txt, w, stdout);#endif
// srand(time(NULL));
// Tread();
// while(T--) {
//
// }nread(); for(i1; in; i) h[i]read(); for(i1; in; i) kread(), s[i]s[i-1]k; for(i1; in; i) c[i]Z(h[i])s[i-1]; for(i1; in; i) debug(%lld , c[i]); debug(\n); Seg.build(rt, 1, 1e6); f[1]0; Seg.add(rt, 1, 1e6, {-2*h[1], f[1]-s[1]Z(h[1])}); i1; debug(y %lldx %lld\n, -2*h[i], f[i]-s[i]Z(h[i])); for(i2; in; i) {f[i]Seg.que(rt, 1, 1e6, h[i])c[i]; Seg.add(rt, 1, 1e6, {-2*h[i], f[i]-s[i]Z(h[i])}); debug(y %lldx %lld\n, -2*h[i], f[i]-s[i]Z(h[i])); }for(i1; in; i) debug(%lld , f[i]); debug(\n); printf(%lld, f[n]); return 0;
}
