Li Chao tree is another technique for solving line queries problem. It is primarily used when we need to add a new line and find the maximum or minimum value at a specific point. This technique leverages the segment tree structure to quickly find the required values.
Li Chao tree differs from CHT in that it is similar to dynamic CHT, adding edges based on any angle coefficient without affecting the result
However, the Li Chao tree cannot work if the input size is too large due to the use of a segment tree (this can be addressed by compressing the numbers).
Since it is a segment tree, the add and get operations have a complexity of log(n).
Explaination:
(L,R), where each node stores the line segment such that mid=(L+R)/2 reaches the maximum or minimum value. Create a segment tree using the struct line
// Li Chao tree structure
struct line
{
ll a, b;
ll operator()(long long x)
{
return a*x+b;
}
};
line st[40*maxn];
void add(int id, int l, int r, line segment)
{
if(l+1==r)
{
if(segment(l)>st[id](l))
swap(segment,st[id]);
}
else
{
int mid = (l+r)/2;
if(st[id].a>segment.a) swap(segment,st[id]);
if(segment(mid)>st[id](mid))
{
swap(segment,st[id]);
add(id*2,l,mid,segment);
}
else
add(id*2+1,mid,r,segment);
}
}
l+1=r is straightforward, we will analyze the remaining case
Mid, we keep the line at the current node and update the right node with the new line (since the new line is better than the old line from the segment Mid → R)
➤ With this approach, we can be sure that during the result retrieval process, we will find the line segment that provides the best value (Read more about the get function for further understanding)
Travel from the root of the tree to the leaf node to find the best possible maximum value
ll get(int id, int l, int r, ll val)
{
if(l+1==r)
return st[id](val);
else
{
int mid = (l+r)/2;
if(val<=mid)
return max(st[id](val),get(id*2,l,mid,val));
else
return max(st[id](val),get(id*2+1,mid,r,val));
}
}
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
const ll inf = 1e18+1;
int n,w[maxn];
ll h[maxn],sum[maxn],dp;
struct line
{
ll a, b;
ll operator()(long long x)
{
return a*x+b;
}
};
line st[40*maxn];
void add(int id, int l, int r, line segment)
{
if(l+1==r)
{
if(segment(l)<st[id](l))
swap(segment,st[id]);
}
else
{
int mid = (l+r)/2;
if(st[id].a>segment.a) swap(segment,st[id]);
if(segment(mid)<st[id](mid))
{
swap(segment,st[id]);
add(id*2+1,mid,r,segment);
}
else
add(id*2,l,mid,segment);
}
}
ll get(int id, int l, int r, ll val)
{
if(l+1==r)
return st[id](val);
else
{
int mid = (l+r)/2;
if(val<=mid)
return min(st[id](val),get(id*2,l,mid,val));
else
return min(st[id](val),get(id*2+1,mid,r,val));
}
}
void input()
{
for(int i=0;i<40*maxn;++i)
{
st[i].a=0;
st[i].b = inf;
}
cin>>n;
for(int i=1;i<=n;++i) cin>>h[i];
for(int i=1;i<=n;++i) cin>>w[i];
for(int i=1;i<=n;++i) sum[i] = sum[i-1]+w[i];
line tmp;
tmp.a = -2*h[1];
tmp.b = h[1]*h[1] - sum[1];
add(1,0,1e6,tmp);
for(int i=2;i<=n;++i)
{
dp = h[i]*h[i] + sum[i-1] + get(1,0,1e6,h[i]);
tmp.a = -2*h[i];
tmp.b = h[i]*h[i] - sum[i] + dp;
add(1,0,1e6,tmp);
}
cout<<dp;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
return 0;
}