#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
using namespace std;
typedef long long ll;
struct Artifact {
int id;
int w;
ll diff; // Cena navíc za to, že je sám (A - B)
};
struct Event {
int w; // Váha hrany nebo dotazu
int type; // 1: Hrana (i, i+1), 2: Hrana (i, i+2), 3: Dotaz
int idx; // Index
// Řazení: Podle váhy. Při shodě vah mají přednost hrany před dotazy (Type 1/2 < Type 3)
bool operator<(const Event& other) const {
if (w != other.w) return w < other.w;
return type < other.type;
}
};
struct DSU {
vector<int> parent;
vector<int> sz; // Velikost komponenty
vector<ll> min_diff[2]; // min_diff[0]: min(A-B) pro sudé indexy, [1] pro liché
vector<int> min_idx; // Nejnižší index v komponentě (určuje paritu majority)
vector<bool> can_swap; // Máme hranu typu 2 (skok)?
ll current_penalty = 0; // Součet penalizací všech LICHÝCH komponent
DSU(int n, const vector<Artifact>& arts) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
sz.assign(n, 1);
min_diff[0].assign(n, 2e18); // Inicializace "nekonečnem"
min_diff[1].assign(n, 2e18);
min_idx.resize(n);
can_swap.assign(n, false);
for(int i=0; i<n; ++i) {
min_diff[i%2][i] = arts[i].diff;
min_idx[i] = i;
// Na začátku je každý sám -> lichá komponenta -> platí diff
current_penalty += arts[i].diff;
}
}
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}
// Vypočítá penalizaci pro jednu konkrétní komponentu
ll get_penalty(int root) {
if (sz[root] % 2 == 0) return 0; // Sudá velikost = 0 penále
// Lichá velikost:
// Komponenta je vždy souvislý interval [L, R] (díky vlastnosti Type 1 hran).
// Majoritní parita (ta, které je o 1 víc) je parita L (min_idx).
int major_parity = min_idx[root] % 2;
ll val = min_diff[major_parity][root]; // Musíme obětovat někoho z majority
if (can_swap[root]) {
// Pokud máme skok, můžeme obětovat někoho z minority, pokud je to levnější
val = min(val, min_diff[1 - major_parity][root]);
}
return val;
}
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
// OPTIMALIZACE: Union by Size (připojujeme menší k většímu)
if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
// Odečteme staré penalizace
current_penalty -= get_penalty(root_i);
current_penalty -= get_penalty(root_j);
// Sloučení (j do i)
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
// Aktualizace vlastností kořene
min_diff[0][root_i] = min(min_diff[0][root_i], min_diff[0][root_j]);
min_diff[1][root_i] = min(min_diff[1][root_i], min_diff[1][root_j]);
min_idx[root_i] = min(min_idx[root_i], min_idx[root_j]);
can_swap[root_i] = can_swap[root_i] | can_swap[root_j];
// Přičteme novou penalizaci spojené komponenty
current_penalty += get_penalty(root_i);
}
}
void activate_swap(int i) {
int root = find(i);
if (!can_swap[root]) {
current_penalty -= get_penalty(root);
can_swap[root] = true;
current_penalty += get_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_B_sum = 0; // Základní cena, kdybychom všechno spárovali (suma B)
for(int i=0; i<n; ++i) {
arts[i] = {i, W[i], (ll)A[i] - B[i]};
base_B_sum += B[i];
}
// Seřadíme artefakty podle váhy
sort(arts.begin(), arts.end(), [](const Artifact& a, const Artifact& b){
return a.w < b.w;
});
vector<Event> events;
events.reserve(2 * n + E.size()); // Prealokace pro rychlost
// Hrany Type 1: (i, i+1)
for(int i=0; i < n-1; ++i) {
events.push_back({arts[i+1].w - arts[i].w, 1, i});
}
// Hrany Type 2: (i, i+2) - Skoky
for(int i=0; i < n-2; ++i) {
events.push_back({arts[i+2].w - arts[i].w, 2, i});
}
// Dotazy
for(int i=0; i < E.size(); ++i) {
events.push_back({E[i], 3, i});
}
sort(events.begin(), events.end());
DSU dsu(n, arts);
vector<ll> results(E.size());
for(const auto& ev : events) {
if (ev.type == 1) {
dsu.unite(ev.idx, ev.idx+1);
} else if (ev.type == 2) {
dsu.activate_swap(ev.idx);
} else {
// Výsledek = Suma B + penalizace za liché prvky
results[ev.idx] = base_B_sum + dsu.current_penalty;
}
}
return results;
}
