#include "meetings.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#define debug(x) #x << " = " << x << '\n'
using ll = long long;
const ll INF = 1e18;
struct RMQ {
int n;
std::vector<int> a;
std::vector<std::vector<int>> rmq;
int myMax(int x, int y) {
if (a[x] == a[y]) {
return x > y? x : y;
} else {
return a[x] > a[y]? x : y;
}
}
RMQ() {}
void build(const std::vector<int> &_a) {
a = _a;
n = (int) a.size();
int lg2 = std::__lg(n);
rmq = std::vector<std::vector<int>>(lg2 + 1, std::vector<int>(n, n));
for (int i = 0; i < n; i++) {
rmq[0][i] = i;
}
for (int j = 1; j <= lg2; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
rmq[j][i] = myMax(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r) {
int k = std::__lg(r - l + 1);
return myMax(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
};
struct Line {
ll a, b;
Line() : a(0), b(+INF) {}
Line(ll a, ll b) : a(a), b(b) {}
ll get(ll x) {
return a * x + b;
}
void add(Line x) {
a += x.a;
b += x.b;
}
};
struct Node {
Line line = Line();
Line lazy = Line(0, 0);
Node *lc = nullptr;
Node *rc = nullptr;
void apply(ll l, ll r, Line v) {
line.add(v);
lazy.add(v);
}
};
Node* root;
int sz;
void init(int n) {
root = new Node();
sz = n;
}
void PushLazy(Node* &n, ll tl, ll tr) {
if (n == nullptr) return;
if (n->lc == nullptr) n->lc = new Node();
if (n->rc == nullptr) n->rc = new Node();
ll mid = (tl + tr) / 2;
n->lc->apply(tl, mid, n->lazy);
n->rc->apply(mid + 1, tr, n->lazy);
n->lazy = Line(0, 0);
}
void minLineKnowingly(Node* &n, ll tl, ll tr, Line x) {
if (n == nullptr) n = new Node();
if (n->line.get(tl) > x.get(tl)) std::swap(n->line, x);
if (n->line.get(tr) <= x.get(tr)) return;
if (tl == tr) return;
ll mid = (tl + tr) / 2;
PushLazy(n, tl, tr);
if (n->line.get(mid) < x.get(mid)) {
minLineKnowingly(n->rc, mid + 1, tr, x);
} else {
std::swap(n->line, x);
minLineKnowingly(n->lc, tl, mid, x);
}
}
void PushLine(Node* &n, ll tl, ll tr) {
if (n == nullptr) return;
ll mid = (tl + tr) / 2;
minLineKnowingly(n->lc, tl, mid, n->line);
minLineKnowingly(n->rc, mid + 1, tr, n->line);
n->line = Line();
}
void minLine(Node* &n, ll tl, ll tr, ll l, ll r, Line x) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (n == nullptr) n = new Node();
if (l <= tl && tr <= r) return minLineKnowingly(n, tl, tr, x);
ll mid = (tl + tr) / 2;
PushLazy(n, tl, tr);
minLine(n->lc, tl, mid, l, r, x);
minLine(n->rc, mid + 1, tr, l, r, x);
}
void addLine(Node* &n, ll tl, ll tr, ll l, ll r, Line x) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (n == nullptr) n = new Node();
if (l <= tl && tr <= r) return n->apply(tl, tr, x);
ll mid = (tl + tr) / 2;
PushLazy(n, tl, tr);
PushLine(n, tl, tr);
addLine(n->lc, tl, mid, l, r, x);
addLine(n->rc, mid + 1, tr, l, r, x);
}
ll pointQuery(Node* &n, ll tl, ll tr, ll x) {
if (n == nullptr) return -INF;
if (tl == tr) return n->line.get(x);
ll res = n->line.get(x);
ll mid = (tl + tr) / 2;
PushLazy(n, tl, tr);
if (x <= mid) {
res = std::min(res, pointQuery(n->lc, tl, mid, x));
} else {
res = std::min(res, pointQuery(n->rc, mid + 1, tr, x));
}
return res;
}
void minLine(int l, int r, Line x) {
return minLine(root, 0, sz - 1, l, r, x);
}
void minLine(int l, int r, ll x, ll y) {
minLine(l, r, Line(x, y));
}
void addLine(int l, int r, Line x) {
return addLine(root, 0, sz - 1, l, r, x);
}
void addConstant(int l, int r, ll c) {
addLine(l, r, Line(0, c));
}
ll pointQuery(int x) {
return pointQuery(root, 0, sz - 1, x);
}
void pointUpdate(int p, ll x) {
addConstant(p, p, x - pointQuery(p));
}
std::vector<ll> minimum_costs(std::vector<int> a, std::vector<int> L, std::vector<int> R) {
int n = (int) a.size();
int q = (int) L.size();
std::vector<ll> answer(q, +INF);
RMQ rmq;
std::vector<std::set<std::pair<int, int>>> lHere(n);
std::vector<std::set<std::pair<int, int>>> rHere(n);
auto solve = [&](auto &self, int l, int r) -> void {
if (l > r) {
return;
}
int p = rmq.query(l, r);
self(self, l, p - 1);
self(self, p + 1, r);
// raspund la query uri
if (p - l < r - p) {
for (int st = l; st <= p; st++) {
// iau mereu l cel mai mare
while (!lHere[st].empty() && (*lHere[st].rbegin()).first >= p) {
auto [dr, index] = *lHere[st].lower_bound({p, 0});
if (dr <= r) {
answer[index] = std::min(answer[index], pointQuery(dr) + (ll) a[p] * (p - st + 1));
lHere[st].erase({dr, index});
rHere[dr].erase({st, index});
} else {
break;
}
}
}
} else {
for (int dr = p; dr <= r; dr++) {
while (!rHere[dr].empty() && (*rHere[dr].rbegin()).first >= l) {
// vreau l minim
auto [st, index] = *rHere[dr].lower_bound({l, 0});
if (st <= p) {
answer[index] = std::min(answer[index], pointQuery(dr) + (ll) a[p] * (p - st + 1));
lHere[st].erase({dr, index});
rHere[dr].erase({st, index});
} else {
break;
}
}
}
}
// acum trebuie sa recalculez pref[l..r]
// pref[l..p-1] ramane la fel
// pref[p]
ll c = p == l? 0 : pointQuery(p - 1);
// if (l == 2 && r == 2) {
// std::cout << debug(DS.pointQuery(2));
// std::cout << debug(c);
// DS.pointUpdate(p, c);
// std::cout << debug(DS.pointQuery(2));
// }
pointUpdate(p, c + a[p]);
// // pref[p+1..r]
addConstant(p + 1, r, (ll) a[p] * (p - l + 1));
minLine(p + 1, r, a[p], c + (ll) a[p] * (-p + 1));
};
auto addQueries = [&]() {
for (int i = 0; i < n; i++) {
lHere[i].clear();
rHere[i].clear();
}
for (int i = 0; i < q; i++) {
lHere[L[i]].insert({R[i], i});
rHere[R[i]].insert({L[i], i});
}
};
auto prepare = [&]() {
init(n);
for (int i = 0; i < n; i++) {
pointUpdate(i, 0);
}
rmq.build(a);
addQueries();
};
prepare();
solve(solve, 0, n - 1);
std::reverse(a.begin(), a.end());
for (int i = 0; i < q; i++) {
L[i] = n - 1 - L[i];
R[i] = n - 1 - R[i];
std::swap(L[i], R[i]);
}
prepare();
solve(solve, 0, n - 1);
return answer;
}
