#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n;
struct Item {
ll w, a, b;
bool operator<(const Item& oth) const {
return w < oth.w;
}
};
struct Events {
vector<int> joins, jumps, queries;
};
struct Range {
int len, first;
ll totb;
array<ll, 2> min_jump_cost; // a - b
array<ll, 2> min_skip_cost; // a - b
ll get_cost() {
if (len % 2 == 0) return totb;
else {
return totb + min(min_jump_cost[1], min_skip_cost[0]);
}
}
Range operator+(const Range& oth) const {
Range res;
res.len = len + oth.len;
res.first = first;
res.totb = totb + oth.totb;
if (len % 2 == 0) {
res.min_jump_cost[0] = min(min_jump_cost[0], oth.min_jump_cost[0]);
res.min_jump_cost[1] = min(min_jump_cost[1], oth.min_jump_cost[1]);
res.min_skip_cost[0] = min(min_skip_cost[0], oth.min_skip_cost[0]);
res.min_skip_cost[1] = min(min_skip_cost[1], oth.min_skip_cost[1]);
} else {
res.min_jump_cost[0] = min(min_jump_cost[0], oth.min_jump_cost[1]);
res.min_jump_cost[1] = min(min_jump_cost[1], oth.min_jump_cost[0]);
res.min_skip_cost[0] = min(min_skip_cost[0], oth.min_skip_cost[1]);
res.min_skip_cost[1] = min(min_skip_cost[1], oth.min_skip_cost[0]);
}
return res;
}
};
Range make_range(int i, ll b, ll a) {
return {
1, i,
b,
{INF, INF},
{a - b, INF}
};
}
struct DSU {
vector<int> e;
vector<Range> ranges;
void init(int n) {
e.resize(n, -1);
ranges.resize(n);
}
int find(int x) {
return e[x] < 0 ? x : e[x] = find(e[x]);
}
Range& get(int x) {
return ranges[find(x)];
}
bool unite(int x, int y) {
x = find(x), y = find(y);
assert(x != y);
ranges[x] = ranges[x] + ranges[y];
e[y] = x;
return true;
}
};
vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
n = size(w);
vector<Item> items(n);
for (int i = 0; i < n; i++) {
items[i] = {w[i], a[i], b[i]};
}
sort(items.begin(), items.end());
map<ll, Events> evs;
for (int i = 0; i < n - 1; i++) {
evs[items[i + 1].w - items[i].w].joins.push_back(i);
}
for (int i = 1; i < n - 1; i++) {
evs[items[i + 1].w - items[i - 1].w].jumps.push_back(i);
}
for (int i = 0; i < e.size(); i++) {
evs[e[i]].queries.push_back(i);
}
DSU dsu;
dsu.init(n);
for (int i = 0; i < n; i++) dsu.ranges[i] = make_range(i, items[i].b, items[i].a);
ll ans = accumulate(a.begin(), a.end(), 0ll);
vector<ll> out(e.size());
for (auto& [curd, events] : evs) {
for (int i : events.joins) {
ans -= dsu.get(i).get_cost();
ans -= dsu.get(i + 1).get_cost();
dsu.unite(i, i + 1);
ans += dsu.get(i).get_cost();
}
for (int i : events.jumps) {
Range& obj = dsu.get(i);
ans -= obj.get_cost();
int j = i - obj.first;
obj.min_jump_cost[j % 2] = min(obj.min_jump_cost[j % 2], items[i].a - items[i].b);
ans += obj.get_cost();
}
for (int i : events.queries) {
out[i] = ans;
}
}
return out;
}
