#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1
*/
ll res = 0;
const int MAXN = 1e5;
ll pmn[MAXN + 1][2];
int l[MAXN];
ll mn[MAXN], sums[MAXN + 1];
ll update(int x);
struct DSU {
vector<int> e;
DSU(int n) {
e = vector<int>(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
int size(int x) {
return -e[get(x)];
}
void unite(int x, int y) {
x = get(x);
y = get(y);
// cout << "MERGING = " << x << " " << y << endl;
if (x == y) return;
res -= update(x);
res -= update(y);
l[x] = min(l[x], l[y]);
sums[x] += sums[y];
// cout << "BEFORE: x | y\n";
// for (int j = 0; j < 2; ++j) {
// cout << pmn[x][j] << " " << pmn[y][j] << endl;
// }
// cout << endl;
for (int j = 0; j < 2; ++j) {
pmn[x][j] = min(pmn[x][j], pmn[y][j]);
}
// cout << "AFTER: x | y\n";
// for (int j = 0; j < 2; ++j) {
// cout << pmn[x][j] << " " << pmn[y][j] << endl;
// }
// cout << endl;
mn[x] = min(mn[x], mn[y]);
e[x] += e[y];
e[y] = x;
res += update(x);
}
} dsu(MAXN + 1);
ll update(int x) {
assert(x == dsu.get(x));
int p = l[x];
return sums[x] + ((dsu.size(x) & 1) ? min(mn[x], pmn[x][p & 1]) : 0);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E) {
int Q = (int)E.size();
int N = W.size();
vector<array<int, 3>> data(N);
for (int i = 0; i < N; ++i) {
data[i] = {W[i], A[i], B[i]};
}
sort(begin(data), end(data));
for (int i = 0; i < N; ++i) {
ll now = data[i][2] - data[i][1];
pmn[i][0] = pmn[i][1] = LLONG_MAX;
pmn[i][i & 1] = -now;
sums[i] = now;
l[i] = i;
mn[i] = LLONG_MAX;
res += data[i][1];
}
// for (int i = 0; i < N; ++i) {
// cout << W[order[i]] << " ";
//
// }
vector<array<int, 3>> events;
vector<ll> R(Q);
for (int i = 0; i < Q; ++i) {
events.push_back({E[i], 2, i});
}
for (int i = 0; i < N - 1; ++i) {
events.push_back({data[i + 1][0] - data[i][0], 0, i});
if (i + 2 < N) {
events.push_back({data[i + 2][0] - data[i][0], 1, i});
}
}
// cout << res << endl;
sort(begin(events), end(events));
// for (auto& e : events) {
// int lst = 0;
// int cnt = 0;
// for (auto& u : e) {
// cnt++;
// if (cnt == 3) cout << u << " ";
// if (cnt == 2)lst = u;
// }
// if (lst == 2) cout << " = query";
// else if (lst == 0) cout << " = (i, i + 1)";
// else cout << " = (i, i + 2)";
// cout << endl;
// }
// cout << endl;
for (auto& e : events) {
if (e[1] == 2) R[e[2]] = res;
else if (e[1] == 0) {
dsu.unite(e[2], e[2] + 1);
} else {
int x = dsu.get(e[2]);
res -= update(x);
int i = e[2] + 1;
ll nw = data[i][1] - data[i][2];
// cout << e[2] << " " << x << " = ";
// cout << mn[x] << " => ";
mn[x] = min(mn[x], nw);
// cout << mn[x] << endl;
res += update(x);
}
// cout << " -> " << res << endl;
}
return R;
}
