#include "nile.h"
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 2e9;
struct CTDL{
int u = 0,v = 0,dist = 0;
bool operator <(const CTDL&other) const{
return (dist < other.dist);
}
};
struct segment_tree{
int seg[4*maxn];
void init(int l,int r,int v){
seg[v] = inf;
if (l == r) return;
int w = (l + r)/2;
init(l,w,2*v + 1);
init(w + 1,r,2*v + 2);
}
void update(int l,int r,int v,int p,int val){
if (l > p || r < p) return;
if (l == r){
seg[v] = min(seg[v],val);
return;
}
int w = (l + r)/2;
update(l,w,2*v + 1,p,val);
update(w + 1,r,2*v + 2,p,val);
seg[v] = min(seg[2*v + 1],seg[2*v + 2]);
}
int calc(int l,int r,int v,int lx,int rx){
if (l > rx || r < lx) return inf;
if (l >= lx && r <= rx) return seg[v];
int w = (l + r)/2;
return min(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
}
} seg[2];
vector <CTDL> lst,skip_list;
int a[maxn],W[maxn],A[maxn],B[maxn];
pir Q[maxn],arr[maxn];
struct DSU{
int par[maxn],M[maxn][2],L[maxn],R[maxn],sz[maxn];
ll sum[maxn],cost[maxn];
int findp(int x){
return (x == par[x]) ? x : par[x] = findp(par[x]);
}
void init(int n){
for (int i = 1 ; i <= n ; i++){
sum[i] = a[i];
sz[i] = 1;
M[i][i % 2] = abs(a[i]);
M[i][(i % 2) ^ 1] = INT_MAX;
L[i] = i;
R[i] = i;
par[i] = i;
cost[i] = 0;
}
}
ll add(int u,int v,int n){
int x = findp(u),y = findp(v);
if (x != y){
ll res = sum[x] + sum[y];
ll tmp = cost[x] + cost[y];
sz[x] += sz[y];
sum[x] += sum[y];
M[x][0] = min(M[x][0],M[y][0]);
M[x][1] = min(M[x][1],M[y][1]);
L[x] = min(L[x],L[y]);
R[x] = max(R[x],R[y]);
par[y] = x;
if (sz[x] % 2){
res += M[x][L[x] % 2];
int id = 1 - (L[x] % 2);
res = min(res,sum[x] + (ll)seg[id].calc(1,n,0,L[x],R[x]));
}
cost[x] = res;
return res - tmp;
}
return 0;
}
ll recalc(int u,int n){
int x = findp(u);
ll tmp = cost[x];
ll res = cost[x];
if (sz[x] % 2 && sz[x] > 1){
int id = (L[x] % 2) ^ 1;
res = min(res,sum[x] + (ll)seg[id].calc(1,n,0,L[x],R[x]));
}
cost[x] = res;
return res - tmp;
}
} dsu;
void prepare(vector <int> W,vector <int> A,vector <int> B,vector <int> E){
int n = W.size();
int q = E.size();
lst.clear();
skip_list.clear();
seg[0].init(1,n,0);
seg[1].init(1,n,0);
//
for (int i = 1 ; i <= n ; i++) arr[i] = {W[i - 1],B[i - 1] - A[i - 1]};
sort(arr + 1,arr + 1 + n);
for (int i = 1 ; i <= n ; i++)
a[i] = arr[i].se;
for (int i = 1 ; i <= q ; i++)
Q[i] = {E[i - 1],i};
sort(Q + 1,Q + 1 + q);
//////
//////// connected components
for (int i = 1 ; i < n ; i++){
lst.push_back({i,i + 1,arr[i + 1].fi - arr[i].fi});
if (i + 2 <= n)
skip_list.push_back({i + 1,i + 1,arr[i + 2].fi - arr[i].fi});
}
sort(skip_list.begin(),skip_list.end());
sort(lst.begin(),lst.end());
dsu.init(n);
///////
}
vector <ll> calculate_costs(vector <int> W,vector <int> A,vector <int> B,vector <int> E){
vector <ll> res;
int n = W.size(),q = E.size();
res.resize(q);
prepare(W,A,B,E);
ll cur = 0;
for (int x : A) cur += x;
int p = 0,p_skip = 0;
for (int i = 1 ; i <= q ; i++){
int D = Q[i].fi,id = Q[i].se;
while (p_skip < skip_list.size() && skip_list[p_skip].dist <= D){
int u = skip_list[p_skip].u;
seg[u % 2].update(1,n,0,u,abs(a[u]));
cur += dsu.recalc(u,n);
p_skip++;
}
while (p < lst.size() && lst[p].dist <= D){
cur += dsu.add(lst[p].u,lst[p].v,n);
p++;
}
res[id - 1] = cur;
}
return res;
}
