#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define pb push_back
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
struct ParTree {
ParTree* lt, *rt;
ll l, r;
pll v;
ParTree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v({INF(ll), INF(ll)}) {}
inline pll combine(pll lv, pll rv) {
return {min(lv.first, rv.first), min(lv.second, rv.second)};
}
void build(const vll& a) {
if(l == r) {
if(l & 0b1ll) {
// odd, put in second
v.second = a[l];
} else {
v.first = a[l];
}
return;
}
ll m = (l + r) >> 1ll;
lt = new ParTree(l, m);
rt = new ParTree(m + 1ll, r);
lt->build(a);
rt->build(a);
v = combine(lt->v, rt->v);
}
pll qry(ll ql, ll qr) {
if(ql > r || qr < l) return {INF(ll), INF(ll)};
if(ql == l && qr == r) return v;
ll m = (l + r) >> 1ll;
return combine(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1ll), qr));
}
};
struct MinTree {
MinTree *lt, *rt;
ll l, r;
ll v;
MinTree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(INF(ll)) {}
inline ll combine(ll lv, ll rv) {
return min(lv, rv);
}
void build(const vll& a) {
if(l == r) {
v = a[l];
return;
}
ll m = (l + r) >> 1ll;
lt = new MinTree(l, m);
rt = new MinTree(m + 1ll, r);
lt->build(a);
rt->build(a);
v = combine(lt->v, rt->v);
}
void upd(ll i, ll nv) {
if(r < i || l > i) return;
if(l == r) {
v = nv;
return;
}
ll m = (l + r) >> 1ll;
if(i <= m) lt->upd(i, nv);
else rt->upd(i, nv);
v = combine(lt->v, rt->v);
}
ll qry(ll ql, ll qr) {
if(ql > r || qr < l) return INF(ll);
if(ql == l && qr == r) return v;
ll m = (l + r) >> 1ll;
return combine(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1ll), qr));
}
};
struct DSU {
/*
DSU must include min and max index of the current component
also, the updates for the values of each component must be separated
into its own function
so every time we update the value in the MinTree, we have to
call update on the corresponding value of the component in DSU
*/
ll n;
ll ncomps;
vll par;
vll csize;
vll minc;
vll cl; // left index of component
vll cr; // right index of component
ll curans;
DSU(ll a_n, ll initans, const vll& a): n(a_n), ncomps(a_n), par(a_n, 0ll), csize(a_n, 1ll), minc(a_n, INF(ll)), cl(a_n, 0ll), cr(a_n, 0ll), curans(initans) {
for(ll i = 0ll; i < n; i++) {
cl[i] = cr[i] = par[i] = i;
minc[i] = a[i];
}
}
ll find(ll i) {
return (i == par[i] ? i : par[i] = find(par[i]));
}
void unify(ll i, ll j, ParTree* ptr, MinTree* mtr, const vll& bpref) {
ll pari = find(i);
ll parj = find(j);
if(pari == parj) return;
ll prev_c = minc[pari] + minc[parj];
ll npar;
if(csize[pari] < csize[parj]) {
// merge i into j
npar = par[pari] = parj;
csize[parj] += csize[pari];
} else {
// merge j into i
npar = par[parj] = pari;
csize[pari] += csize[parj];
}
cl[npar] = min(cl[pari], cl[parj]);
cr[npar] = max(cr[pari], cr[parj]);
minc[npar] = prev_c;
upd(npar, ptr, mtr, bpref);
}
void upd(ll comp, ParTree* ptr, MinTree* mtr, const vll& bpref) {
comp = find(comp);
ll prval = minc[comp];
// compute new cost
// we must do casework on the size of the component
ll cursz = csize[comp];
if(cursz & 0b1ll) {
// odd
ll startpar = cl[comp] & 0b1ll;
pll alt_min_pair = ptr->qry(cl[comp], cr[comp]);
ll alt_min = (startpar ? alt_min_pair.second : alt_min_pair.first);
minc[comp] = min(alt_min, mtr->qry(cl[comp], cr[comp])) + bpref[cr[comp] + 1ll] - bpref[cl[comp]];
} else {
// even
minc[comp] = bpref[cr[comp] + 1ll] - bpref[cl[comp]];
// cerr << "!! " << minc[comp] << endl;
}
// update total cost
curans -= prval;
curans += minc[comp];
}
};
struct Query {
ll qi, e;
};
typedef vector<Query> vq;
struct Artifact {
ll w, a, b;
};
typedef vector<Artifact> va;
vll calculate_costs(vi w, vi a, vi b, vi e) {
ll n = (ll)w.size();
ll q = (ll)e.size();
vll ans(q, 0);
// Sorting queries into a vector for offline processing
vq qs;
for(ll i = 0ll; i < q; i++) {
qs.pb({i, e[i]});
}
sort(qs.begin(), qs.end(), [](Query q1, Query q2) {return q1.e < q2.e;});
// Storing artifacts in new format and sorting
va arts;
for(ll i = 0ll; i < n; i++) {
arts.pb({w[i], a[i], b[i]});
}
sort(arts.begin(), arts.end(), [](Artifact v1, Artifact v2) {return v1.w < v2.w;});
// Creating prefsum arrays for a and b
vll prefa(n + 1ll, 0ll);
for(ll i = 0ll; i < n; i++) {
prefa[i + 1ll] = prefa[i] + arts[i].a;
}
vll prefb(n + 1ll, 0ll);
for(ll i = 0ll; i < n; i++) {
prefb[i + 1ll] = prefb[i] + arts[i].b;
}
// Creating vec of (diff, ind) pairs for updating MinTree
vpll mintrupds;
for(ll i = 1ll; i < n - 1ll; i++) {
mintrupds.pb({arts[i + 1ll].w - arts[i - 1ll].w, i});
}
/// sort mintrupds by INCREASING order
sort(mintrupds.begin(), mintrupds.end());
// creating vec of (diff, ind) pairs for updating DSU
vpll dsuupds;
for(ll i = 0ll; i < n - 1ll; i++) {
dsuupds.pb({arts[i + 1ll].w - arts[i].w, i});
}
sort(dsuupds.begin(), dsuupds.end());
// Building Segtrees and DSU
/// Building a[i] - b[i]
vll amb(n, 0ll);
for(ll i = 0ll; i < n; i++) amb[i] = arts[i].a - arts[i].b;
/// building partree
ParTree* ptr = new ParTree(0ll, n - 1ll);
ptr->build(amb);
/// mintree should store a[i] - b[i], initially INF
MinTree* mtr = new MinTree(0ll, n - 1ll);
vll mtrinit(n, INF(ll));
mtrinit[0ll] = arts[0ll].a - arts[0ll].b;
mtrinit[n - 1ll] = arts[n - 1ll].a - arts[n - 1ll].b;
mtr->build(mtrinit);
/// building DSU
vll art_a_vals(n, 0ll);
for(ll i = 0ll; i < n; i++) art_a_vals[i] = arts[i].a;
DSU dsu(n, prefa[n], art_a_vals);
// Answering queries offline
ll qi = 0ll;
ll mtrupdind = 0ll;
ll dsuupdind = 0ll;
while(qi < q) {
ll curd = qs[qi].e;
// update the DSU
while(dsuupdind < n - 1ll && dsuupds[dsuupdind].first <= curd) {
// cerr << "! " << dsuupds[dsuupdind].first << endl;
ll updind = dsuupds[dsuupdind].second;
dsu.unify(updind, updind + 1ll, ptr, mtr, prefb);
dsuupdind++;
}
// update the MinTree
while(mtrupdind < n - 2ll && mintrupds[mtrupdind].first <= curd) {
ll updind = mintrupds[mtrupdind].second;
mtr->upd(updind, arts[updind].a - arts[updind].b);
dsu.upd(dsu.find(updind), ptr, mtr, prefb);
mtrupdind++;
}
// answer
ans[qs[qi].qi] = dsu.curans;
qi++;
}
return ans;
}
