#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1e18 + 1e16; struct SegmentTree { struct Matrix { vector <vector <ll>> arr; Matrix() { arr.resize(3); for (int i = 0; i < 3; ++i) arr[i].resize(3, 0); } Matrix(ll x) { arr.resize(3); for (int i = 0; i < 3; ++i) arr[i].resize(3); arr[0][0] = x; arr[0][1] = inf; arr[0][2] = inf; arr[1][0] = 0; arr[1][1] = inf; arr[1][2] = inf; arr[2][0] = inf; arr[2][1] = 0; arr[2][2] = inf; } }; int n; vector <Matrix> t; SegmentTree() = default; SegmentTree(int n): n(n) { t.resize(4 * n); } ll calc(vector <vector <ll>> &a, int i, vector <vector <ll>> &b, int j) { return min({a[i][0] + b[0][j], a[i][1] + b[1][j], a[i][2] + b[2][j]}); } Matrix merge(Matrix &a, Matrix &b) { Matrix c; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { c.arr[i][j] = calc(a.arr, i, b.arr, j); } } return c; } void build(int v, int l, int r, vector <int> &A) { if (r - l == 1) { t[v] = Matrix(A[l]); return; } int m = (l + r) / 2; build(2 * v + 1, l, m, A); build(2 * v + 2, m, r, A); t[v] = merge(t[2 * v + 2], t[2 * v + 1]); } void build(vector <int> &A) { build(0, 0, n, A); } void update(int v, int l, int r, int pos, int d, int x) { if (r - l == 1) { t[v].arr[0][d] = x; return; } int m = (l + r) / 2; if (pos < m) { update(2 * v + 1, l, m, pos, d, x); } else { update(2 * v + 2, m, r, pos, d, x); } t[v] = merge(t[2 * v + 2], t[2 * v + 1]); } void update(int pos, int d, int x) { update(0, 0, n, pos, d, x); } ll get() { return t[0].arr[0][0]; } }; struct quest { int ind; int d; int t; // 0 - update1, 1 - update2, 2 - get quest() = default; quest(int ind, int d, int t): ind(ind), d(d), t(t) {} bool operator<(const quest &oth) const { return tie(d, t) < tie(oth.d, oth.t); } }; vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) { int n = A.size(); int p[n]; iota(p, p + n, 0); sort(p, p + n, [&](int i, int j) { return W[i] < W[j]; }); vector <int> nW(n); vector <int> nA(n); vector <int> nB(n); for (int i = 0; i < n; ++i) { nW[i] = W[p[i]]; nA[i] = A[p[i]]; nB[i] = B[p[i]]; } W = move(nW); A = move(nA); B = move(nB); ll sm = 0; for (int i = 0; i < n; ++i) sm += B[i]; for (int i = 0; i < n; ++i) A[i] -= B[i]; vector <quest> qs; if (n >= 2) { qs.push_back(quest(1, W[1] - W[0], 0)); } for (int i = 2; i < n; ++i) { qs.push_back(quest(i, W[i] - W[i - 2], 1)); qs.push_back(quest(i, W[i] - W[i - 1], 0)); } int q = E.size(); vector <ll> R(q); for (int i = 0; i < q; ++i) { qs.push_back(quest(i, E[i], 2)); } SegmentTree t(n); t.build(A); sort(qs.begin(), qs.end()); for (quest e : qs) { if (e.t <= 1) { t.update(e.ind, e.t + 1, e.t * A[e.ind - 1]); } else { R[e.ind] = t.get() + sm; } } return R; }