#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
const long long INF = (long long)1e18;
struct segment_tree{
vector<int> st, v;
int maxn;
int get(int x, int y){
if(x == maxn) return y;
if(y == maxn) return x;
return v[x] >= v[y] ? x : y;
}
void init(vector<int> ert, int n){
maxn = n;
while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
v = ert;
st.resize(maxn<<1, maxn);
iota(st.begin()+maxn, st.begin()+maxn+n, 0);
for(int i = maxn-1; i > 0; i--)
st[i] = get(st[2*i], st[2*i+1]);
}
int query(int s, int e, int x, int l, int r){
if(e <= l || r <= s)
return maxn;
if(s <= l && r <= e)
return st[x];
int m = (l+r)/2;
return get(query(s, e, 2*x, l, m), query(s, e, 2*x+1, m, r));
}
int query(int l, int r){
return query(l, r, 1, 0, maxn);
}
};
struct egyenes{
long long m, b;
egyenes(){}
egyenes(long long m, long long b) : m(m), b(b) {}
long long ertek(long long x) { return m*x+b; }
};
struct lichao_tree{
vector<egyenes> st;
vector<long long> prop;
int maxn;
void init(int n){
maxn = n;
while(maxn != (maxn&(-maxn))) maxn += (maxn&(-maxn));
st.assign(maxn<<1, egyenes(0, INF));
prop.assign(maxn<<1, 0);
}
void propagate(int x){
st[x].b += prop[x];
if(x < maxn){
prop[2*x] += prop[x];
prop[2*x+1] += prop[x];
}
prop[x] = 0;
}
void add(egyenes e, int x, int l, int r){
propagate(x);
int m = (l+r)/2;
bool bal = e.ertek(l) < st[x].ertek(l);
bool koz = e.ertek(m) < st[x].ertek(m);
if(koz) swap(st[x], e);
if(l+1 == r) return;
if(bal == koz)
add(e, 2*x+1, m, r);
else
add(e, 2*x, l, m);
}
void update(int s, int e, egyenes eg, int x, int l, int r){
propagate(x);
if(e <= l || r <= s)
return;
if(s <= l && r <= e){
//cout<<"insert line "<<l<<" "<<r<<"\n";
add(eg, x, l, r);
return;
}
int m = (l+r)/2;
update(s, e, eg, 2*x, l, m);
update(s, e, eg, 2*x+1, m, r);
}
void update(int l, int r, egyenes e) { update(l, r, e, 1, 0, maxn); }
void update_lines(int s, int e, long long c, int x, int l, int r){
propagate(x);
if(e <= l || r <= s)
return;
if(s <= l && r <= e){
prop[x] += c;
return;
}
int m = (l+r)/2;
update_lines(s, e, c, 2*x, l, m);
update_lines(s, e, c, 2*x+1, m, r);
}
void update_lines(int l, int r, long long c) { update_lines(l, r, c, 1, 0, maxn); }
long long query(int ind, int x, int l, int r){
propagate(x);
if(l+1 == r)
return st[x].ertek(ind);
int m = (l+r)/2;
if(ind < m)
return min(st[x].ertek(ind), query(ind, 2*x, l, m));
return min(st[x].ertek(ind), query(ind, 2*x+1, m, r));
}
long long query(int x) { return query(x, 1, 0, maxn); }
};
struct adat{
int ind, l, r;
};
struct node{
int l, r, lc, rc;
long long ert;
vector<adat> querys;
node *L = nullptr, *R = nullptr;
node(){}
node(node *L, node *R, int l, int r, int lc, int rc) : L(L), R(R), l(l), r(r), lc(lc), rc(rc) {};
};
typedef node* gnode;
segment_tree maxST;
lichao_tree lichao;
vector<int> h;
gnode build(int l, int r, int lc, int rc){
if(l+1 == r){
gnode temp = new node(nullptr, nullptr, l, r, lc, rc);
temp->ert = h[l];
return temp;
}
int m = maxST.query(l, r);
int c = h[m];
if(m == l) m++;
gnode p = new node(build(l, m, lc, c), build(m, r, c, rc), l, r, lc, rc);
p->ert = min(p->L->ert + (long long)(r-m)*c, p->R->ert + (long long)(m-l)*c);
return p;
}
void kiir(gnode p){
cout<<"node: ("<<(p->l)<<", "<<(p->r)<<") ert: "<<p->ert<<" cl: "<<p->lc<<" cr: "<<p->rc<<"\n";
}
vector<vector<adat>> vegek((int)1e6);
vector<long long> meg;
int starts[(int)1e6];
gnode buffer[(int)1e6];
void add_node(gnode os, gnode p, int ind){
long long ossz = (long long)(p->r-p->l)*p->rc;
if(h[p->l] > p->rc) ossz += (long long)(h[p->l] - p->rc);
//cout<<"node add: "<<p->r<<" "<<os->r<<"\n";
lichao.update_lines(p->r, os->r, ossz);
lichao.update(p->r, os->r, {p->rc, p->ert-(long long)p->rc*p->r});
return;
}
void bejar(gnode p, int len){
//kiir(p);
if(p->l+1 == p->r){
for(adat d : vegek[p->l]){
int m = lower_bound(starts, starts+len, d.l)-starts;
if(m == len) continue;
buffer[m]->querys.push_back(d);
}
return;
}
bejar(p->L, len);
starts[len] = p->l;
buffer[len] = p->L;
bejar(p->R, len+1);
//if(p->L->l == 1 && p->L->r == 4)
add_node(p, p->L, len);
for(adat d : p->L->querys){
//cout<<"query: ---------------------------\n";
//kiir(p->L);
//cout<<d.r+1<<" ind\n";
meg[d.ind] = min(meg[d.ind], lichao.query(d.r+1) + (long long)(p->L->l-d.l)*p->lc);
}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
H.push_back((int)1e9+1);
H.insert(H.begin(), (int)1e9+1);
int n = (int)H.size();
int q = (int)L.size();
h = H;
meg.assign(q, INF);
vegek.assign((int)1e6, vector<adat>());
maxST.init(H, n);
lichao.init(n);
for(int i = 0; i < q; i++)
vegek[R[i]+2].push_back({i, L[i]+1, R[i]+1});
bejar(build(0, n, 0, 0), 0);
for(int i = 0; i < q; i++)
vegek[R[i]+2].clear();
reverse(h.begin(), h.end());
maxST.init(h, n);
for(int i = 0; i < q; i++)
vegek[n-L[i]-1].push_back({i, n-R[i]-2, n-L[i]-2});
bejar(build(0, n, 0, 0), 0);
return meg;
}
