#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; }