#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// 定义一个足够小的值代替负无穷大，避免相加时溢出
const long long MINF = -1000000000000000000LL;
// 3x3 矩阵结构体，用于动态DP的转移
struct Matrix {
long long mat[3][3];
Matrix() {
for(int i = 0; i < 3; ++i)
for(int j = 0; j < 3; ++j)
mat[i][j] = MINF;
}
};
// 矩阵乘法，(max, +) 半环下的乘法
Matrix multiply(const Matrix& A, const Matrix& B) {
Matrix C;
for(int i = 0; i < 3; ++i) {
for(int k = 0; k < 3; ++k) {
if (A.mat[i][k] == MINF) continue;
for(int j = 0; j < 3; ++j) {
if (B.mat[k][j] == MINF) continue;
if (C.mat[i][j] < A.mat[i][k] + B.mat[k][j]) {
C.mat[i][j] = A.mat[i][k] + B.mat[k][j];
}
}
}
}
return C;
}
// 手工艺品结构体
struct Item {
long long w, a, b;
bool operator<(const Item& other) const {
return w < other.w;
}
};
// 查询结构体
struct Query {
long long d;
int id;
bool operator<(const Query& other) const {
return d < other.d;
}
};
// 边 / 转移 事件结构体
struct Event {
long long d;
int type; // 2 代表相邻成对, 3 代表相隔一个成对
int k;
long long val;
bool operator<(const Event& other) const {
return d < other.d;
}
};
vector<Matrix> tree;
// 初始化构建线段树
void build(int node, int l, int r) {
if (l == r) {
tree[node].mat[0][0] = 0;
tree[node].mat[1][0] = 0;
tree[node].mat[2][1] = 0;
return;
}
int mid = l + (r - l) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
// 注意：按顺序应该是右边的矩阵乘上左边的矩阵
tree[node] = multiply(tree[2 * node + 1], tree[2 * node]);
}
// 单点更新矩阵中的某个状态
void update(int node, int l, int r, int idx, int type, long long val) {
if (l == r) {
if (type == 2) tree[node].mat[0][1] = val;
else if (type == 3) tree[node].mat[0][2] = val;
return;
}
int mid = l + (r - l) / 2;
if (idx <= mid) update(2 * node, l, mid, idx, type, val);
else update(2 * node + 1, mid + 1, r, idx, type, val);
tree[node] = multiply(tree[2 * node + 1], tree[2 * node]);
}
std::vector<long long> calculate_costs(
std::vector<int> W_in, std::vector<int> A_in,
std::vector<int> B_in, std::vector<int> E_in) {
int N = W_in.size();
int Q = E_in.size();
long long sum_A = 0;
vector<Item> items(N);
for(int i = 0; i < N; ++i) {
items[i] = {W_in[i], A_in[i], B_in[i]};
sum_A += A_in[i];
}
// 按重量升序排序
sort(items.begin(), items.end());
vector<long long> ans(Q);
// 特判边界：只有一个手工艺品时永远无法成对
if (N == 1) {
for(int i = 0; i < Q; ++i) ans[i] = sum_A;
return ans;
}
vector<Query> queries(Q);
for(int i = 0; i < Q; ++i) {
queries[i] = {E_in[i], i};
}
// 将查询离线并按 D 升序排序
sort(queries.begin(), queries.end());
vector<Event> events;
// 收集相邻两个打包的事件
for(int k = 1; k < N; ++k) {
long long d = items[k].w - items[k-1].w;
long long val = items[k-1].a + items[k].a - items[k-1].b - items[k].b;
events.push_back({d, 2, k, val});
}
// 收集相隔一个打包的事件
for(int k = 2; k < N; ++k) {
long long d = items[k].w - items[k-2].w;
long long val = items[k-2].a + items[k].a - items[k-2].b - items[k].b;
events.push_back({d, 3, k, val});
}
// 将事件按所需满足的重量差 D 升序排序
sort(events.begin(), events.end());
// 线段树维护区间矩阵的乘积，叶子从 1 到 N-1
tree.assign(4 * N, Matrix());
build(1, 1, N - 1);
int event_idx = 0;
int num_events = events.size();
for(int i = 0; i < Q; ++i) {
long long current_d = queries[i].d;
// 把满足当前 D 的所有边/转移加进线段树
while(event_idx < num_events && events[event_idx].d <= current_d) {
update(1, 1, N - 1, events[event_idx].k, events[event_idx].type, events[event_idx].val);
event_idx++;
}
// 提取最终保存的最大节省费用
long long max_save = tree[1].mat[0][0];
max_save = max(max_save, tree[1].mat[0][1]);
max_save = max(max_save, tree[1].mat[0][2]);
// 最终结果 = 假设全独立的总花费 - 最大化节省的花费
ans[queries[i].id] = sum_A - max_save;
}
return ans;
}
