#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
// x -> a * x + b
const int64_t OFFSET_SENTINEL = INT64_MIN + 1557;
struct LinearMap {
int64_t a;
int64_t b;
LinearMap operator()(const LinearMap& rhs) {
if (a == OFFSET_SENTINEL) return {rhs.a, rhs.b + b};
return *this;
}
int64_t operator()(const int64_t rhs) { return a * rhs + b; }
};
struct SegTree {
// if lazy.a == OFFSET_SENTINEL: x -> x+lazy.b
// else x -> lazy.a * i + lazy.b
vector<LinearMap> lazy;
// seg holds leftmost val;
vector<LinearMap> seg;
int n;
void _build(int node, int l, int r, vector<int>& src) {
seg[node] = {0, src[l]};
int m = (l + r) / 2;
_build(2 * node + 1, l, m, src);
_build(2 * node + 2, m, r, src);
}
void build(vector<int>& src) {
n = src.size();
lazy.assign(4 * n, {OFFSET_SENTINEL, 0});
seg.assign(4 * n, {0, 0});
}
void propagate(int node, int l, int r) {
if (l + 1 == r) return;
seg[2 * node + 1] = lazy[node](seg[2 * node + 1]);
lazy[2 * node + 1] = lazy[node](lazy[2 * node + 1]);
seg[2 * node + 2] = lazy[node](seg[2 * node + 2]);
lazy[2 * node + 2] = lazy[node](lazy[2 * node + 2]);
lazy[node] = {OFFSET_SENTINEL, 0};
}
void _apply_range(int node, int l, int r, int ql, int qr, LinearMap& f) {
if (ql <= l && r <= qr) {
lazy[node] = f(lazy[node]);
seg[node] = f(seg[node]);
return;
}
if (qr <= l || r <= ql) return;
propagate(node, l, r);
int m = (l + r) / 2;
_apply_range(2 * node + 1, l, m, ql, qr, f);
_apply_range(2 * node + 2, m, r, ql, qr, f);
seg[node] = seg[2 * node + 1];
}
void apply_range(int l, int r, LinearMap f) {
_apply_range(0, 0, n, l, r, f);
}
int _search_left(int node, int l, int r, int ql, int qr, LinearMap& f) {
propagate(node, l, r);
if (l + 1 == r) {
if (f(l) < seg[node](l)) return l;
return r;
}
int m = (l + r) / 2;
if (ql <= m && m < qr) {
LinearMap fm = seg[2 * node + 2];
if (f(m) < fm(m)) {
return _search_left(2 * node + 1, l, m, ql, qr, f);
} else {
return _search_left(2 * node + 2, m, r, ql, qr, f);
}
} else if (m < ql) {
return _search_left(2 * node + 2, m, r, ql, qr, f);
} else {
return _search_left(2 * node + 1, l, m, ql, qr, f);
}
}
int _search_right(int node, int l, int r, int ql, int qr, LinearMap& f) {
propagate(node, l, r);
if (l + 1 == r) {
if (f(l) < seg[node](l)) return l;
return l - 1;
}
int m = (l + r) / 2;
if (ql <= m && m < qr) {
LinearMap fm = seg[2 * node + 2];
if (f(m) < fm(m)) {
return _search_right(2 * node + 2, m, r, ql, qr, f);
} else {
return _search_right(2 * node + 1, l, m, ql, qr, f);
}
} else if (m < ql) {
return _search_right(2 * node + 2, m, r, ql, qr, f);
} else {
return _search_right(2 * node + 1, l, m, ql, qr, f);
}
}
// smallest i s.t. LinearMap(i) < seg[i]
int search_left(int l, int r, LinearMap f) {
return _search_left(0, 0, n, l, r, f);
}
// biggest i s.t. LinearMap(i) < seg[i]
int search_right(int l, int r, LinearMap f) {
return _search_right(0, 0, n, l, r, f);
}
int64_t _value(int node, int l, int r, int i) {
propagate(node, l, r);
if (l == i) return seg[node](i);
int m = (l + r) / 2;
if (i >= m)
return _value(2 * node + 2, m, r, i);
else
return _value(2 * node + 1, l, m, i);
}
int64_t value(int i) {
if (i == n) {
cout << "FAIL\n";
}
return _value(0, 0, n, i);
}
};
struct RMQ {
vector<vector<int>> sparse;
vector<int>* src;
void build(vector<int>* _src) {
src = _src;
sparse.emplace_back(src->size(), 0);
for (int i = 0; i < src->size(); ++i) {
sparse[0][i] = i;
}
for (int i = 2, li = 1; i < 2 * src->size(); i = 2 * i, li += 1) {
sparse.emplace_back(src->size(), 0);
for (int j = 0; j + i <= src->size(); ++j) {
int lidx = sparse[li - 1][j];
int ridx = sparse[li - 1][j + i / 2];
sparse[li][j] = (*src)[lidx] < (*src)[ridx] ? ridx : lidx;
}
}
}
int rmq(int l, int r) {
int k = __lg(r - l);
int lidx = sparse[k][l];
int ridx = sparse[k][r - (1 << k)];
return (*src)[lidx] < (*src)[ridx] ? ridx : lidx;
}
};
vector<long long> minimum_costs(vector<int> h, vector<int> ql, vector<int> qr) {
int n = h.size(), q = ql.size();
vector<long long> ans(q);
vector<vector<int>> assigned_queries(n);
// dp_left: r fixed, dp_right: l fixed
SegTree dp_left, dp_right;
dp_left.build(h), dp_right.build(h);
RMQ rmq;
rmq.build(&h);
for (int i = 0; i < q; ++i) {
qr[i] += 1;
assigned_queries[rmq.rmq(ql[i], qr[i])].push_back(i);
}
function<void(int, int)> traverse = [&](int l, int r) {
if (l >= r) return;
int64_t m = rmq.rmq(l, r);
traverse(l, m);
traverse(m + 1, r);
for (auto q : assigned_queries[m]) {
int cl = ql[q], cr = qr[q];
int64_t lmax = cl == m ? 0 : dp_left.value(cl);
int64_t rmax = cr - 1 == m ? 0 : dp_right.value(cr - 1);
ans[q] = min(lmax + h[m] * (cr - m), rmax + h[m] * (m - cl + 1));
}
// merge dp_left and dp_right
// dp_left[l..]
// dp_left[l..=m] = min(dp_left[l..=m] + h[m] * (r - m), dp_left[m + 1] +
// (m
// - i + 1) * h[m])
int64_t value_r = m == r - 1 ? 0 : dp_left.value(m + 1);
int64_t value_l = m == l ? 0 : dp_right.value(m - 1);
if (m == r - 1) {
// if (l == 0 && r == 4) {
// int x = 3;
// }
dp_left.apply_range(l, m, {OFFSET_SENTINEL, h[m]});
dp_left.apply_range(m, m + 1, {0, h[m]});
} else {
// if (l == 1 && r == 4) {
// int x = 3;
// }
dp_left.apply_range(m, m + 1, {0, value_r + h[m]});
// cout << "dpl: ";
// for (int i = 0; i < n; ++i) {
// cout << dp_left.value(i) << " ";
// }
// cout << "\n";
dp_left.apply_range(l, m, {OFFSET_SENTINEL, h[m] * (r - m)});
// cout << "dpl: ";
// for (int i = 0; i < n; ++i) {
// cout << dp_left.value(i) << " ";
// }
// cout << "\n";
int idx = dp_left.search_left(l, m, {-h[m], value_r + (m + 1) * h[m]});
dp_left.apply_range(idx, m, {-h[m], value_r + (m + 1) * h[m]});
// cout << "dpl: ";
// for (int i = 0; i < n; ++i) {
// cout << dp_left.value(i) << " ";
// }
// cout << "\n";
}
if (m == l) {
dp_right.apply_range(m + 1, r, {OFFSET_SENTINEL, h[m]});
dp_right.apply_range(m, m + 1, {0, h[m]});
} else {
dp_right.apply_range(m, m + 1, {0, value_l + h[m]});
dp_right.apply_range(m + 1, r, {OFFSET_SENTINEL, h[m] * (m - l + 1)});
int idx =
dp_right.search_right(m + 1, r, {h[m], value_l - h[m] * (m - 1)});
dp_right.apply_range(m + 1, idx + 1, {h[m], value_l - h[m] * (m - 1)});
}
// cout << l << ", " << r << "\n";
// cout << "dpl: ";
// for (int i = 0; i < n; ++i) {
// cout << dp_left.value(i) << " ";
// }
// cout << "\ndpr: ";
// for (int i = 0; i < n; ++i) cout << dp_right.value(i) << " ";
// cout << "\n";
};
traverse(0, n);
return ans;
}
#ifndef EVAL
#include "grader.cpp"
#endif
