#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
// Struktura pro reprezentaci artefaktu po seřazení
struct Artifact {
int id;
int w, a, b;
ll diff; // cena navíc za to, že je sám (A - B)
};
// Struktura pro DSU (Disjoint Set Union)
struct DSU {
vector<int> parent;
vector<int> sz; // velikost komponenty
// min_p[0] ukládá min(A-B) pro prvky s globálním sudým indexem v této komponentě
// min_p[1] ukládá min(A-B) pro prvky s globálním lichým indexem
vector<ll> min_p[2];
vector<bool> can_swap; // Existuje uvnitř komponenty hrana délky 2?
// Globální součet penalizací (pro liché komponenty)
ll total_penalty = 0;
DSU(int n, const vector<Artifact>& arts) {
parent.resize(n);
iota(all(parent), 0);
sz.assign(n, 1);
min_p[0].assign(n, 2e18); // Inicializace nekonečnem
min_p[1].assign(n, 2e18);
can_swap.assign(n, false);
for(int i=0; i<n; ++i) {
min_p[i%2][i] = arts[i].diff; // Nastavíme počáteční diff
total_penalty += arts[i].diff; // Na začátku jsou všichni sami (ostrůvky velikosti 1)
}
}
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}
// Pomocná funkce pro výpočet penalizace konkrétní komponenty (reprezentované kořenem root)
ll get_component_penalty(int root) {
if (sz[root] % 2 == 0) return 0; // Sudá délka -> všichni spárovaní, žádné penále
// Lichá délka: Musíme nechat jednoho samotného.
// Standardně musí mít stejnou paritu jako "většina" v komponentě.
// Ale DSU neví, kde komponenta začíná, tak to určíme trikem:
// V liché komponentě je počet sudých a lichých indexů různý.
// Ten typ indexu, kterého je víc, je "většinový".
// Protože min_p[0] a min_p[1] drží globální parity, stačí porovnat,
// která parita má víc "zástupců"? Ne, to je složité sledovat.
// Jednodušší: V liché komponentě o 1 prvku (index i) je "většina" parita (i%2).
// Při spojování (SUDÁ + LICHÁ -> LICHÁ) se parita většiny nemění.
// Při spojování (LICHÁ + LICHÁ -> SUDÁ) penále zmizí.
// Takže nám stačí vědět, jakou paritu má "většina".
// Ale my ani to nepotřebujeme.
// V liché komponentě existuje jedna parita, která má o 1 prvek víc.
// Řekněme, že parita P je majoritní. Musíme obětovat někoho z P.
// Pokud máme swap, můžeme obětovat někoho z !P.
// Jak poznat majoritní paritu?
// Při inicializaci (velikost 1, index i) je majorita (i%2).
// Uložíme si typ majority do DSU?
// Ne, stačí sledovat min_p.
// Pro liché komponenty vždy platí: Jeden typ parity je "nucený" (ten co má víc prvků).
// V našem kódu níže budeme merge provádět opatrně a paritu si odvodíme.
// Vlastně: Artifacty jsou seřazené. Komponenta je vždy INTERVAL [L, R].
// Pokud je délka liché, majoritní parita je L%2.
// Ale DSU nedrží L a R. Ale my víme, že hrany jsou jen (i, i+1).
// Takže v každé komponentě je `min_index` ten L.
// Můžeme si držet `min_index` v DSU.
return 0; // Placeholder, logika je přímo v unite/activate
}
// Protože get_component_penalty je složitější implementovat čistě,
// budeme udržovat `total_penalty` inkrementálně při operacích.
// Abychom to zvládli, potřebujeme uvnitř DSU vědět, která parita je ta "hlavní".
// Přidáme si do DSU `start_index`.
vector<int> start_index;
// Pro konstruktor: start_index[i] = i;
// Skutečná funkce pro výpočet penále:
ll calc_penalty(int root) {
if (sz[root] % 2 == 0) return 0;
int majority_parity = start_index[root] % 2;
ll cost = min_p[majority_parity][root]; // Cena když obětujeme někoho z majority
if (can_swap[root]) {
cost = min(cost, min_p[1 - majority_parity][root]);
}
return cost;
}
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
// Odečteme staré penále
total_penalty -= calc_penalty(root_i);
total_penalty -= calc_penalty(root_j);
// Merge (union by size/random, here simply attach j to i)
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
// Update minim
min_p[0][root_i] = min(min_p[0][root_i], min_p[0][root_j]);
min_p[1][root_i] = min(min_p[1][root_i], min_p[1][root_j]);
// Update swap a start index (start index je min z obou)
can_swap[root_i] = can_swap[root_i] | can_swap[root_j];
start_index[root_i] = min(start_index[root_i], start_index[root_j]);
// Přičteme nové penále
total_penalty += calc_penalty(root_i);
}
}
void activate_swap(int i) {
int root = find(i);
if (!can_swap[root]) {
total_penalty -= calc_penalty(root);
can_swap[root] = true;
total_penalty += calc_penalty(root);
}
}
};
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int n = W.size();
vector<Artifact> arts(n);
ll base_cost = 0; // Součet všech B (kdyby bylo vše spárováno)
for(int i=0; i<n; ++i) {
arts[i] = {i, W[i], A[i], B[i], (ll)A[i] - B[i]};
base_cost += B[i];
}
sort(all(arts), [](const Artifact& a, const Artifact& b){
return a.w < b.w;
});
// Eventy: {weight, type, index}
// Type 1: Edge (i, i+1) -> weight = W[i+1] - W[i]
// Type 2: Edge (i, i+2) -> weight = W[i+2] - W[i]
// Type 3: Query -> weight = E[i]
struct Event {
int w, type, idx;
bool operator<(const Event& other) const {
if (w != other.w) return w < other.w;
return type < other.type; // Nejdřív hrany (1,2), pak dotazy (3)
}
};
vector<Event> events;
for(int i=0; i < n-1; ++i) {
events.push_back({arts[i+1].w - arts[i].w, 1, i});
}
for(int i=0; i < n-2; ++i) {
events.push_back({arts[i+2].w - arts[i].w, 2, i});
}
for(int i=0; i < E.size(); ++i) {
events.push_back({E[i], 3, i});
}
sort(all(events));
// Inicializace DSU
// Pozor: DSU potřebuje pracovat s indexy v poli `arts` (0..n-1), ne původními ID
// Ale protože jsme sortovali `arts`, indexy 0..n-1 v DSU odpovídají seřazenému poli.
// Musíme ale správně nastavit start_index
DSU dsu(n, arts);
dsu.start_index.resize(n);
iota(all(dsu.start_index), 0);
vector<ll> results(E.size());
for(auto& ev : events) {
if (ev.type == 1) {
// Spojení i a i+1
dsu.unite(ev.idx, ev.idx+1);
} else if (ev.type == 2) {
// Aktivace swapu pro komponentu obsahující i (a tím pádem i i+2)
// Poznámka: Pokud hrana (i, i+2) je aktivní, pak (i, i+1) a (i+1, i+2)
// jsou zaručeně taky aktivní (díky trojúhelníkové nerovnosti na 1D přímce).
// Takže i a i+2 jsou už ve stejné komponentě.
dsu.activate_swap(ev.idx);
} else {
// Query
results[ev.idx] = base_cost + dsu.total_penalty;
}
}
return results;
}
