#include "nile.h"
#include <vector>
#include <algorithm>
using namespace std;
const int DIM = 1e5;
const long long INF = 1e16;
struct event
{
long long val;
int pos, ch;
};
vector <event> ev;
struct elem
{
long long w, a, b;
};
elem v[DIM + 1];
vector <long long> sol;
struct DSU
{
int t[DIM + 1], sz[DIM + 1];
long long dlt[DIM + 1][2], dlt2[DIM + 1][2]; ///0 -> impar, 1 -> par
long long sol;
void init (int n)
{
for (int i = 0; i < n; i++)
{
t[i] = i;
sz[i] = 1;
dlt[i][0] = v[i].a - v[i].b;
dlt[i][1] = dlt2[i][0] = dlt2[i][1] = INF;
sol += v[i].a;
}
}
int rad (int x)
{
if (x == t[x])
return x;
return t[x] = rad (t[x]);
}
void reun (int x, int y)
{
if (x > y)
swap (x, y);
x = rad (x), y = rad (y);
t[y] = x;
if (sz[y] % 2 != 0)
sol -= min (dlt[y][0], dlt2[y][1]);
if (sz[x] % 2 != 0)
sol -= min (dlt[x][0], dlt2[x][1]);
if (sz[x] % 2 != 0)
{
swap (dlt[y][0], dlt[y][1]);
swap (dlt2[y][0], dlt2[y][1]);
}
for (int i = 0; i < 2; i++)
{
dlt[x][i] = min (dlt[x][i], dlt[y][i]);
dlt2[x][i] = min (dlt2[x][i], dlt2[y][i]);
}
sz[x] += sz[y];
if (sz[x] % 2 != 0)
sol += min (dlt[x][0], dlt2[x][1]);
}
void update (int pos, long long d)
{
int x = rad (pos);
if (sz[x] % 2 != 0)
sol -= min (dlt[x][0], dlt2[x][1]);
if ((pos - x + 1) % 2 == 0)
dlt2[x][1] = min (dlt2[x][1], d);
else
dlt2[x][0] = min (dlt2[x][0], d);
if (sz[x] % 2 != 0)
sol += min (dlt[x][0], dlt2[x][1]);
}
long long get_sol ()
{
return sol;
}
};
DSU dsu;
/**
Daca doua elemente consecutive nu se pot cupla intre ele => putem sa le impartim in intervale disjuncte, pe care le rezolvam separat.
Pt un interval, daca este de lg para, luam tot, altfel tb sa eliminam un element.
Daca tb sa eliminam, daca alegem de pe pozitie impara, doar il taiem. Daca alegem de pe pozitie para, tb sa se cupleze elementele din stanga si din dreapta.
Tinem evenimente de reunire, de activare a unei pozitii si query.
Daca taiem un element par nu putem reuni stanga si dreapta.
Tinem evenimente de activare pt fiecare pozitie.
Cand combinam, delta din stanga si delta din dreapta.
**/
bool cmp (event a, event b)
{
if (a.val == b.val)
return a.ch < b.ch;
return a.val < b.val;
}
bool cmpv (elem a, elem b)
{
return a.w < b.w;
}
void get_events (int n)
{
for (int i = 0; i < n - 1; i++)
ev.push_back ({v[i + 1].w - v[i].w, i, 1});
for (int i = 1; i < n - 1; i++)
ev.push_back ({v[i + 1].w - v[i - 1].w, i, 2});
sort (ev.begin (), ev.end (), cmp);
}
void solve ()
{
for (int i = 0; i < (int) ev.size (); i++)
{
int ch = ev[i].ch, pos = ev[i].pos;
if (ch == 1)
{
dsu.reun (pos, pos + 1);
}
else if (ch == 2)
{
dsu.update (pos, v[pos].a - v[pos].b);
}
else if (ch == 3)
sol[pos] = dsu.get_sol ();
}
}
std::vector<long long> calculate_costs (std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> Q)
{
int n = (int) W.size ();
for (int i = 0; i < n; i++)
v[i] = {W[i], A[i], B[i]};
sort (v, v + n, cmpv);
dsu.init (n);
int q = (int) Q.size ();
sol.resize (q);
for (int i = 0; i < q; i++)
ev.push_back ({Q[i], i, 3});
get_events (n);
solve ();
return sol;
}
