#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 100000; int pred[MAXN]; int sz[MAXN]; int min_c[MAXN]; int min2_c[MAXN]; ll cur_add = 0; int get(int v) { if (v == pred[v]) return v; return pred[v] = get(pred[v]); } void unite(int v, int u) { v = get(v); u = get(u); if (sz[v] & 1) cur_add -= min_c[v]; if (sz[u] & 1) cur_add -= min_c[u]; if (sz[v] > sz[u]) { swap(min_c[v], min_c[u]); swap(min2_c[v], min2_c[u]); swap(v, u); } bool f = (sz[u] & 1); pred[v] = u; sz[u] += sz[v]; // min_c[u] = min(min_c[u], min_c[v]); if (f) { min2_c[u] = min(min2_c[u], min_c[v]); min_c[u] = min(min_c[u], min2_c[v]); } else { min_c[u] = min(min_c[u], min_c[v]); min2_c[u] = min(min2_c[u], min2_c[v]); } if (sz[u] & 1) cur_add += min_c[u]; } vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) { struct event { int t; // 0 - update, 1 - get int ind; int d; event(int t, int ind, int d): t(t), ind(ind), d(d) {} bool operator<(const event &oth) const { return tie(d, t) < tie(oth.d, oth.t); } }; int n = A.size(); fill(sz, sz + n, 1); iota(pred, pred + n, 0); vector <event> es; for (int i = 0; i < E.size(); ++i) { es.push_back(event(1, i, E[i])); } int p[n]; iota(p, p + n, 0); sort(p, p + n, [&](int i, int j) { return W[i] < W[j]; }); for (int i = 1; i < n; ++i) { es.push_back(event(0, i - 1, abs(W[p[i]] - W[p[i - 1]]))); } vector <int> C(n); for (int i = 0; i < n; ++i) C[i] = A[i] - B[i]; for (int i = 0; i < n; ++i) min_c[i] = C[i]; for (int i = 0; i < n; ++i) min2_c[i] = 1e9; for (int i = 0; i < n; ++i) cur_add += C[i]; ll sm = 0; for (int i = 0; i < n; ++i) { sm += B[i]; } sort(es.begin(), es.end()); vector <ll> ans(E.size()); for (event e : es) { if (e.t == 0) { unite(p[e.ind], p[e.ind + 1]); } else if (e.t == 1) { ans[e.ind] = sm + cur_add; } } return ans; }