李超线段树 学习笔记
引入
最近一直在做斜率优化的题，然而只会傻傻维护凸包，一到横坐标不单调，就涉及到手打平衡树，但是我实在不想学平衡树了，所以就准备掏出解决处理直线的大宝贝——李超线段树
功能
有两种操作：
插入一条表达式为 $ L : y = k\times x+b$ 的直线，给出 \(k,b\)。
给出 \(t\)，求当前所有直线中与直线 \(x = t\) 交点的纵坐标最大是多少
实现
原理
维护区间的中点对应的最大值的直线，用到了标记永久化的思想
维护方法
修改
（偷了两张CSDN博主的图）
如当前情况，蓝色的直线是我们加入的直线，如果它比这个区间所有的都大（完全覆盖），那么就把原有线段换成这条直线；反之则直接舍弃。
下一种情况就是不完全覆盖（有交点）
-
首先对于当前这个大区间，现在应该取 \(f(mid )\) 更大的直线作为当前区间的标记，那么对于整个区间都是如此吗？
-
No，可以看到两条直线在 \([l,mid]\) 之间是存在交点的， 那么在左区间的某个位置，\(f(mid')\) 的大小关系就可能发生变化，所以我们需要递归进入有交点的区间来进一步修改
查询
和标记永久化的线段树查询一样，我们查询一个位于 \(x=t\) 的点对应的最大函数值，就要一直从 \([1,n]\) 的直线，一直查询到 \([t,t]\) 的直线，最后取所有可能的最大值，如下图：
我们要把橙色、绿色、蓝色、黄色区间的直线之间所有的最大值都取到。
例题
分析
例题用Build Bridges作为板子，本题写出来的状态转移方程是：
\[f_i=min(f_j+(h_i-h_j)^2+sumw_{i-1}-sumw_{j}) \]按照正常斜率优化的套路写出来的话，原式就变成了：
\[f_i=(h_i^2+s_{i-1})+(-2h_i)h_j+(f_j+h_j^2-sumw_j) \]这时候你发现我们要作为斜率的\((-2h_i)\)并不单调了，而且插入的点 \((h_i,f_i+h_i^2-sumw_i)\)横坐标也不是单调的，所以这个时候就要把方程换一种写法然后使用李超线段树了：
\[f_i=(h_i^2+s_{i-1})+(-2h_j)h_i+(f_j+h_j^2-sumw_j) \]可以发现前面是常数项，后面很像一个直线的形式了，我们可以看成给出一个横坐标，求 \(y=(-2h_j)x+(f_j+h_j^2-sumw_j)\)的最小值。
其中我们每给出一条直线，就看成插入 \(k_i=-2h_i,b_i=f_i+h_i^2-sumw_i\)的一条\(y=k_ix+b_i\)的直线，并且在插入之前查询之前存在的所有直线，使得当前的横坐标\(h_i\)对应能取得最小值对应的函数值，然后再插入这条直线。
注意一开始要让\(k[0]=b[0]=INF\)，不然第一条直线甚至都无法插入
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn=1e5+100;
const int maxm=1e6+10;
int n,h[maxn],w[maxn],sumw[maxn],f[maxn];
int k[maxn],b[maxn];
int rt[maxm<<2];
inline int calc(int x/*横坐标*/,int idx/*编号*/){return k[idx]*x+b[idx];}
inline int K(int j){return -2*h[j];}
inline int B(int j){return f[j]+h[j]*h[j]-sumw[j];}
inline int X(int i){return h[i];}
inline void insert(int x,int l,int r,int idx)
{
if(l==r){if(calc(l,idx)<calc(l,rt[x]))rt[x]=idx;return ;}
int mid=l+r>>1;
if(calc(mid,idx)<calc(mid,rt[x]))swap(idx,rt[x]);//完全覆盖
if(calc(l,idx)<calc(l,rt[x]))insert(x<<1,l,mid,idx);//左区间可能更新
if(calc(r,idx)<calc(r,rt[x]))insert(x<<1|1,mid+1,r,idx);//右区间可能更新
}
inline int query(int x,int l,int r,int x_given)
{
if(l==r)return calc(x_given,rt[x]);
int mid=l+r>>1;
int nex=x_given<=mid?query(x<<1,l,mid,x_given):query(x<<1|1,mid+1,r,x_given),now=calc(x_given,rt[x]);
return min(now,nex);//所有包含x_given 的最大值并
}
void input()
{
scanf("%lld",&n),b[0]=1e18;
for(register int i=1;i<=n;++i)scanf("%lld",&h[i]);
for(register int i=1;i<=n;++i)scanf("%lld",&w[i]),sumw[i]=sumw[i-1]+w[i];
k[1]=K(1),b[1]=B(1),insert(1,0,maxm,1);
}
signed main()
{
input();
for(register int i=2;i<=n;++i)
{
f[i]=h[i]*h[i]+sumw[i-1]+query(1,0,maxm,X(i));
k[i]=K(i),b[i]=B(i),insert(1,0,maxm,i);
}
printf("%lld",f[n]);
return 0;
}