李超线段树

你们太强了 or 我们讲快了
所以我来制作一份美味的加餐

定义

首先我们先明确一下李超线段树可以做什么：

它可以维护多条一次函数，有两个操作：

插入
插入一条一次函数
时间复杂度 $O(\log^2 n)$
查询
查询对于所有存在的一次函数，在 $x=x_0$ 处 $y$ 的最值（最小值/最大值）
时间复杂度 $O(\log n)$

可以给出模版题

例题

洛谷 P4097 【模板】李超线段树 / [HEOI2013] Segment

考虑如何做这两种操作：

插入

我们以最大值为例（例题）

李超线段树是一颗特殊的线段树，其每个节点所代表的区间 $[l,r]$ 是对于在数轴上 $l$ 点到 $r$ 点。

线段树上每个节点维护其所支配区间 $[l,r]$ $x=\frac {l+r} {2}$ 处的最高点的 $y$ 所取的函数（线段）编号。
对于区间 $l$~$r$ ，插入一条新线段（红）。

该线段与区间 $l$~$r$ 没有交集
因此对区间内维护的最优线段没有影响；

该线段与区间 $l$~$r$ 有交集，但区间不是该线段定义域的子集
此时考虑递归到该区间的左右子区间作进一步细化处理；

区间 $l$~$r$ 是该线段定义域的子集
此时分三种情况分类讨论原区间 $l$~$r$ 中的最优线段和新加线段的位置关系：
(红色为新线段，黑色为老线段即原最优线段）

新线段在老线段的上方时：直接更新即可。

新线段在老线段的下方时：丢弃。
新线段和老线段交叉时：
设点 $x$ 是线段树上的一个节点，$mid$ 是 $x$ 所代表的区间的中点。
原来，使$y$取到最大值的直线编号是 $t[x]$ (即黑色线段），现在新增的直线编号是 $now$ （即红色线段）。
我们比较在区间中点 $mid$ 两条线段对应的纵坐标谁大，将大的那条作为新的最优线段（即老线段）。
但由于这两条线段相互之间都不能被对方完全覆盖，所以考虑将没成为最优线段的那条线段往该区间的左右子区间下放，作递归处理（只需要往有比最优线段更优的一端递归即可）。

如图：

红色的线段为新线段，黑色的线段为老线段（即原最优线段），比较两个线段上当$x=mid$时$y$的大小，发现新线段的$y$更大，交换新线段和老线段。
如图

判断可知新线段（即红色线段）的左区间端点比老线段要大，递归更新左区间。判断出右区间新线段不优，即不能对答案做出贡献，丢弃。

每一次都只会修改左右区间中的$1$个，时间复杂度为$O(\log^2n)$。

我们发现李超线段树的特点其一就是对于一次插入操作并没有将改后的数据下传，我们把这种对 区间修改、单点查询 起效的方法称作“标记永久化”。

但查询时也要做一些特殊操作

查询

李超线段树只能实现单点查询。

由于上文插入中的标记永久化的存在，查询时需要从根节点一直询问到叶节点，这一条链上的任意一个点所维护的一次函数标号都可能是答案。

具体的，我们需要对查找 $x$ 时走到的整条路径上的所有节点维护的答案取最值。

代码实现

code

#include<bits/stdc++.h>
using namespace std;
#define ls (ro<<1)
#define rs (ro<<1|1)
const double eps=1e-10;//调精度
const int mod=39989;
const int _mod=1e9;
int n,op,k,xx,xy,yx,yy;
int ans,lastans,lcnt;
struct jade
{double k,b;//直线参数 
}line[100010];//线段 
struct seek
{int l,r,id;//区间左右端点//编号 
}t[400010];
//李超线段树 
void build(int ro,int l,int r)
{t[ro].l=l;t[ro].r=r;if(l==r){return ;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);
}
double gety(int i,int x)//计算纵坐标 
{return line[i].k*x+line[i].b;
}
bool cmp(int i,int j,int x)//比较编号为 i 和 j 的线段在 X 处的纵坐标 
{if(gety(i,x)-gety(j,x)>eps){return 1;}if(gety(j,x)-gety(i,x)>eps){return 0;}return i<j;
}
void insert(int ro,int id)//插入直线，编号为 id 
{if(cmp(id,t[ro].id,t[ro].l)&&cmp(id,t[ro].id,t[ro].r))//该直线比当前区间最优线段完全更优 {t[ro].id=id;return ;}if(cmp(id,t[ro].id,t[ro].l)==0&&cmp(id,t[ro].id,t[ro].r)==0)//该直线比当前区间最优线段完全更劣{return ;}//两线段有交点，都不能完全覆盖彼此int mid=(t[ro].l+t[ro].r)>>1;if(cmp(id,t[ro].id,mid)){swap(id,t[ro].id);}//处理左右子区间 if(cmp(id,t[ro].id,t[ro].l)){insert(ls,id);}if(cmp(id,t[ro].id,t[ro].r)){insert(rs,id);}return ;
}
void add(int ro,int l,int r,int id)
{if(t[ro].r<l||t[ro].l>r)//线段与该区间不交{return ;	 }	if(l<=t[ro].l&&r>=t[ro].r)//线段完全覆盖该区间,区间是该线段定义域的子集{insert(ro,id);return ;}//线段覆盖部分该区间 //处理左右子区间 add(ls,l,r,id);add(rs,l,r,id);
} 
void query(int ro,int x)
{if(t[ro].r<x||t[ro].l>x){return ;}if(cmp(t[ro].id,ans,x))//比较路径上的最优线段，记录编号 {ans=t[ro].id;}if(t[ro].l==t[ro].r){return ;}//在树上往下查询最优线段query(ls,x);query(rs,x);
}
int main()
{cin>>n;build(1,1,mod);for(int i=1;i<=n;i++){cin>>op;if(op==0){cin>>k;k=(k+lastans-1)%mod+1;ans=0;query(1,k);cout<<ans<<endl;lastans=ans;}else{cin>>xx>>xy>>yx>>yy;xx=(xx+lastans-1)%mod+1;yx=(yx+lastans-1)%mod+1;xy=(xy+lastans-1)%_mod+1;yy=(yy+lastans-1)%_mod+1;if(yx<xx){swap(xx,yx);swap(xy,yy);}lcnt++;if(yx!=xx){line[lcnt].k=1.0*(yy-xy)/(yx-xx);line[lcnt].b=1.0*xy-line[lcnt].k*xx;}else//特殊处理竖直线段{line[lcnt].k=0;line[lcnt].b=max(xy,yy);}add(1,xx,yx,lcnt);}}return 0;
}

经典实现是将插入操作分为两部分 $insert$ 和 $add$ ，分开处理线段与区间的交集情况。
$add$ 处理线段与区间的关系，若完全覆盖则调用 $insert$ 加入线段，此时因区间全覆盖所以只传参 $id$ 和 $ro$ 。
反之则 $add$ 函数向左右儿子递归。

我们发现，如果线段树维护的是直线，则使用 $O(\log n)$ 做法即可完成修改操作，因为不用判断区间，多用于DP优化方面。

李超线段树优化DP

例题

洛谷 P4655 [CEOI 2017] Building Bridges

考虑定义状态 $dp_i$ 表示对于搭建到第 $i$ 根柱子的最小代价。

我们钦定 $sum_x$ 表示 $\sum_{i=1}^x w_i$

考虑状态转移方程有

\[dp_i=min\{dp_j+(h_i-h_j)^2+sum_{i-1}-sum_{j}\} \]

朴素转移是 $n^2$ 的，不能通过。
考虑将这个方程化简有：

\[dp_i=min\{dp_j+h_i^2+h_j^2-2*h_i*h_j+sum_{i-1}-sum_{j}\} \]

考虑将与 $j$ 无关的项提出来，有：

\[dp_i=h_i^2+sum_{i-1}+min\{dp_j+h_j^2-2*h_i*h_j-sum_{j}\} \]

我们将 $-2*h_j$ 看成 $k$ ，将 $dp_j+h_j^2-sum_{j} $看成 $b$ ，将 $h_i$ 看成 $x$ 。

我们就可以将枚举取 $min$ 中的所有项看成 $i-1$ 条关于 $h_i$ 的一次函数求最小值，这正好可以使用李超线段树。

具体的，考虑从小到大枚举每一个 $i$ ，对于当前 $i$ 使用李超线段树的查询求出 $dp_i$ 的值，再将 $i$ 所形成的一次函数 $k$ 和 $b$ 插入到李超线段树中。

特别的，$dp_1=0$，直接将其插入到李超线段树中即可。

我们考虑时间复杂度，上文提出在李超线段树中插入直线复杂度为 $O(\log n)$，与外层循环嵌套，时间复杂度为 $O(n\log n)$。

代码实现

code

#include<bits/stdc++.h>
using namespace std;
#define ls (ro<<1)
#define rs (ro<<1|1)
struct jade
{long long k,b;
}le[100010];//直线 
struct seek
{long long l,r,x;
}t[4000100];//李超线段树 
long long gy(long long x,long long id)//计算对应函数id在x处的y值 
{return le[id].k*x+le[id].b;
}
long long h[100010],w[100010],f[100010];//题目所给的h，w，dp值 
void build(long long ro,long long l,long long r)
{t[ro].l=l;t[ro].r=r;if(l==r){return ;}long long mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);	
}
void insert(long long ro,long long x)//插入一条直线 
{if(t[ro].l==t[ro].r)//叶节点 {if(gy(t[ro].l,x)<gy(t[ro].l,t[ro].x)){t[ro].x=x;}return ;}long long mid=(t[ro].l+t[ro].r)>>1;if(gy(mid,x)<gy(mid,t[ro].x)) {swap(x,t[ro].x);}if(gy(t[ro].l,x)<gy(t[ro].l,t[ro].x)){insert(ls,x);}if(gy(t[ro].r,x)<gy(t[ro].r,t[ro].x)){insert(rs,x);}
}
long long query(long long ro,long long x)//查询答案 
{if(t[ro].l==t[ro].r){return gy(x,t[ro].x);}long long mid=(t[ro].l+t[ro].r)>>1;long long res=INT_MAX;if(x<=mid){res=query(ls,x); }else{res=query(rs,x);}return min(res,gy(x,t[ro].x));
}
int main()
{long long n;cin>>n;le[0].b=1e18;for(long long i=1;i<=n;i++){cin>>h[i];}for(long long i=1;i<=n;i++){cin>>w[i];w[i]+=w[i-1];//前缀和 }le[1].k=-2*h[1];le[1].b=h[1]*h[1]-w[1];build(1,0,1000010);insert(1,1);//插入初始线段 for(long long i=2;i<=n;i++){long long x=h[i];f[i]=h[i]*h[i]+w[i-1]+query(1,x);//计算当前dp值 le[i].k=-2*h[i];le[i].b=f[i]+h[i]*h[i]-w[i];insert(1,i);//插入当前线段 }cout<<f[n];return 0;	
}