李超树记

Eterna · 2026-01-22 08:02:35 · 算法·理论

例题 1

在平面直角坐标系下维护 n 次操作：

1. 在平面上加入一条线段。
2. 给定数 k，询问与直线 x = k 相交的线段中，交点纵坐标最大线段的编号。

强制在线。

对 x 轴建立线段树的结构。

在每个线段树的结点上维护最优线段，满足：

1. 线段的定义域包含了当前结点表示的区间 [l,r]。
2. 该线段在满足 1. 的线段中，在区间中点 M=\left \lfloor \dfrac{l+r}{2} \right \rfloor 的点值最大。

之前不是最优线段的线段显然不会在后续变为最优线段，所以插入线段时只需讨论新线段与原最优线段之间的关系即可。

通过维护最优线段，单次查询取表示 [x,x] 到线段树根节点上的所有最优线段即可。这里可以理解为标记永久化。

假如插入线段不在目前的区间成为最优线段，不难发现它在目前区间的子区间中还可能成为最优线段。否则，交换原最优线段与插入线段，因为原最优线段被新线段顶掉，但是在子区间还可能成为新的最优线段。

如图中的绿色最优线段，它在红色区间不是最优线段但却是红色区间的子区间的最优线段。

记插入线段为 f，最优线段为 g。在上述处理后，一定有 f(M)<g(M)。

若 g(l)>f(l),g(r)>f(r)，显然 f 不论在左边还是右边都不如 g，直接不要了。

若 g(l)<f(l),g(r)>f(r)，与上图情况相同，其可能在左区间成为最优线段，而右区间不可能。向左区间递归插入。

若 g(l)>f(l),g(r)<f(r)，同理，只有右区间可能以 f 为最优。向右区间递归插入。

可见我们每次最多向一边递归，最多的递归层数只有线段树的深度，所以在一个结点上插入复杂度为 \mathcal{O}(\log V)。插入一条线段涉及 \mathcal{O}(\log V) 个结点。

故单次插入是 \mathcal{O}(\log^2 V)，总时间复杂度为 \mathcal{O}(n \log^2 V)

#include<bits/stdc++.h>
#define db double
#define pb pair<db,int>
#define int long long
#define rd read()
#define gc getchar()
using namespace std;
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const db eps=1e-6;
const int N=100005,V=39989;
db k[N],b[N];int cnt,n,E[N<<2];
inline db gt(int id,int x){
    return b[id]+x*k[id];
}
inline pb max(pb a,pb b){
    if(a.first-b.first>eps)return a;
    if(b.first-a.first>eps)return b;
    return a.second<b.second?a:b;
}
inline void push(int id,int l,int r,int v){
    int mid=l+r>>1;if(gt(v,mid)-gt(E[id],mid)>eps)swap(v,E[id]);
    if(gt(v,l)-gt(E[id],l)>eps||abs(gt(v,l)-gt(E[id],l))<=eps&&v<E[id])push(id<<1,l,mid,v);
    if(gt(v,r)-gt(E[id],r)>eps||abs(gt(v,r)-gt(E[id],r))<=eps&&v<E[id])push(id<<1|1,mid+1,r,v);
}
inline void U(int id,int l,int r,int x,int y,int v){
    if(x<=l&&y>=r)return push(id,l,r,v);int mid=l+r>>1;
    if(x<=mid)U(id<<1,l,mid,x,y,v);if(y>mid)U(id<<1|1,mid+1,r,x,y,v);   
}
inline pb Q(int id,int l,int r,int x){
    if(l==r)return {gt(E[id],x),E[id]};int mid=l+r>>1;
    return max(x<=mid?Q(id<<1,l,mid,x):Q(id<<1|1,mid+1,r,x),{gt(E[id],x),E[id]});
}
signed main(){
    b[0]=-1e15,n=rd;
    for(int i=1,op,K,lst=0;i<=n;++i){
        op=rd;
        if(op==0)
            K=(rd+lst-1)%39989+1,
            cout<<(lst=Q(1,1,V,K).second)<<'\n';
        else{
            int x=(rd+lst-1)%39989+1,y=(rd+lst-1)%1000000000+1,
            X=(rd+lst-1)%39989+1,Y=(rd+lst-1)%1000000000+1;
            if(x>X)swap(x,X),swap(y,Y);
            if(x==X)k[++cnt]=0,b[cnt]=max(y,Y);
            else k[++cnt]=(y-Y)*1.0/(x-X),b[cnt]=y-x*k[cnt];
            U(1,1,V,x,X,cnt);
        }
    }
    return 0;
}

例题 2

请自行阅读题面。

首先可以发现，每次买入和卖出一定会全部买完或卖完。因为如果买或卖一点能赚，全部用完一定可以赚更多。

考虑动态规划。

记 f_i 为前 i 天后剩的最大钱数。用这 f_i 元，可以买 x_i=\dfrac{f_i\mathrm{Rate}_i}{a_i\mathrm{Rate}_i+b_i} 个 A 卷，y_i=\dfrac{f_i}{a_i\mathrm{Rate}_i+b_i} 个 B 卷。

在卖出这些卷之前，我们分文不剩，所以中间不会再有购入。

可以得到转移 f_i=\max\{f_{i-1},\max \limits _{j=1}^{i-1} x_ja_i+y_jb_i\}。

经典的，我们将 x_ja_i+y_jb_i 除以 b_i，得到 f_i=\max\{f_{i-1},b_i\max \limits _{j=1}^{i-1} \dfrac{a_ix_j}{b_i}+y_j\}。

这样 \max 里的就是一个一次函数的结构。每次查 x=\dfrac{a_i}{b_i} 处的最大值即可，使用李超树维护。

将所有的 \dfrac{a_i}{b_i} 离散化可以在一定程度上提高精度，减小常数。时间复杂度为 \mathcal{O}(n \log n)。

#include<bits/stdc++.h>
#define pr pair<double,int> 
#define db double
#define int long long
#define rd read()
using namespace std;
const int N=100005;const db eps=1e-6;
int n,P[N],E[N<<2];
db s,f[N],a[N],b[N],ro[N],B[N],k[N],p[N];
inline db gt(int id,int x){
    return k[id]*p[x]+B[id];
}
inline void U(int id,int l,int r,int v){
    int mid=l+r>>1;
    if(gt(v,mid)-gt(E[id],mid)>eps)swap(v,E[id]);
    if(gt(v,l)-gt(E[id],l)>eps)U(id<<1,l,mid,v);
    if(gt(v,r)-gt(E[id],r)>eps)U(id<<1|1,mid+1,r,v);
}
inline double Q(int id,int l,int r,int x){
    if(l==r)return gt(E[id],x);int mid=l+r>>1;
    return max(x<=mid?Q(id<<1,l,mid,x):Q(id<<1|1,mid+1,r,x),gt(E[id],x));
}
signed main(){
    cin>>n>>s;B[0]=-1e15;
    for(int i=1;i<=n;P[i]=p[i]=a[i]/b[i],++i)cin>>a[i]>>b[i]>>ro[i];
    sort(p+1,p+n+1);for(int i=1;i<=n;++i)P[i]=lower_bound(p+1,p+n+1,a[i]/b[i])-p;
    f[1]=s,B[1]=f[1]/(a[1]*ro[1]+b[1]),k[1]=B[1]*ro[1];
    U(1,1,n,1);
    for(int i=2;i<=n;++i)
        f[i]=max(f[i-1],b[i]*Q(1,1,n,P[i])),
        B[i]=f[i]/(a[i]*ro[i]+b[i]),k[i]=B[i]*ro[i],
        U(1,1,n,i);
    printf("%.3lf\n",f[n]);return 0;
}

例题 3

给定一棵 n 个结点的树，从一个点 x 跳到其子树中非其本身的点 y 的代价是 a_xb_y。对于每个结点，求出从它开始，跳到任意叶子结点的最小代价。

自下而上 dp，记 f_i 为从 x 跳到叶子的最小代价。

容易得到 f_x = \min\limits _{i \in \mathrm{subtree(x)}}f_i+a_xb_i。直接出现了一次函数。

所以我们维护当前子树的李超树，每次查询子树中函数 a_x 处的最值即可。

构建可以启发式合并做到 \mathcal{O}(n \log n \log V)，可以通过。但是这非常简单，相信大家都会。

既然李超树是线段树，那么它同样可以线段树合并。与一般标记永久化的线段树的线段树合并比较类似，我们还需考虑最优线段的合并，我们只能调用插入，因为合并上去的最优线段同样可能成为其他结点的最优线段。

这样用线段树合并的方法分析复杂度，调用了 \mathcal{O}(n \log n) 次插入，难道复杂度是 \mathcal{O}(n \log n \log V)？

其实不是，对于合并时同一个结点在两棵线段树上都有最优线段时，合并后至少其中一条最优线段被下移。对于一条被下移的最优线段，它在线段树上的深度至少加一。故一条线段最多下移 \mathcal{O}(\log n) 次。

则我们的复杂度是 \mathcal{O}(n (\log n+\log V))。

#include<bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
const int N=100005,V=100000;
int n,cnt,a[N],b[N],f[N],rt[N];
vector<int> v[N];
struct node{
    int ls,rs,E;
}t[N<<5];
inline int gt(int id,int x){
    return b[id]*x+f[id];
}
inline void U(int &id,int l,int r,int v){
    if(!id)id=++cnt;int mid=l+r>>1,e=t[id].E;
    if(gt(v,mid)>gt(e,mid))e=v,swap(v,t[id].E);
    if(gt(v,l)>gt(e,l))U(t[id].ls,l,mid,v);
    if(gt(v,r)>gt(e,r))U(t[id].rs,mid+1,r,v);
}
inline int Q(int id,int l,int r,int x){
    if(l==r)return gt(t[id].E,x);int mid=l+r>>1;
    return max(x<=mid?Q(t[id].ls,l,mid,x):Q(t[id].rs,mid+1,r,x),gt(t[id].E,x));
}
inline int merge(int x,int y,int l,int r){
    if(!x||!y)return x|y;int mid=l+r>>1;U(x,l,r,t[y].E);
    t[x].ls=merge(t[x].ls,t[y].ls,l,mid);
    t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r);
    return x;
}
inline void sol(int x,int fa){
    for(int i:v[x])
        if(i!=fa)sol(i,x),rt[x]=merge(rt[x],rt[i],-V,V);
    f[x]=Q(rt[x],-V,V,a[x]);if(v[x].size()==1&&x!=1)f[x]=0;
    U(rt[x],-V,V,x);
}
signed main(){
    cin>>n;f[0]=-1e18;
    for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;b[i]*=-1,++i)cin>>b[i];
    for(int i=1,x,y;i<n;++i)cin>>x>>y,v[x].push_back(y),v[y].push_back(x);
    sol(1,0);for(int i=1;i<=n;++i)cout<<-f[i]<<' ';
    return 0;
}

例题 4

给定一棵 n 个结点的树，边有边权。从一个结点 v 跳到其任意距离 d \le l_v 的祖先代价是 dp_v+q_v。求从每个结点开始，跳到根的最小代价。

与上题相反，我们从上往下 dp。用 d_x 表示根到 x 的距离。

容易直接写出转移方程 f_x = \min\limits _{i \in \mathrm{Ancestor(x)},d_x-d_i \le l_x}-d_ip_x+d_xp_x+f_i+q_x。

其实就是找最小的 -d_ip_x+f_i，发现又是一次函数。

与前面的题不同之处在于本题有 d_i-d_x \le l_i 还有一维祖先的限制。

同时满足这两个条件的点显然是条链，可以简单二分求出。

处理出出栈序，设结点 x 第 t_x 个离开 DFS。考虑在 DFS 依次插入一次函数，而一条链 (u,v) 只需查区间 [t_u,t_v] 即可。

例如上图，其中结点标号与出栈序同，不难发现不在链 (4,8) 上的结点不是不被 [t_4,t_8] 包含就是还没 DFS 到。所以我们不需要撤销已经插入的一次函数。

考虑更加严格的证明。首先对于 x 的祖先 y，它们在出栈序上的区间 [t_x,t_y] 一定包含了链 (x,y) 的所有点，而 y 的祖先一定不被包含。之后才访问到的且不在链上的点因为没有插入所以不论是否包含都没关系。之前访问过且不在链上的点，在访问到 x 之前必然经过了一次回溯，所以出栈序 <t_x。

所以现在就是将李超树的查询从全局扩展到了区间，考虑使用线段树套李超树维护出栈序维即可。

复杂度显然是 \mathcal{O}(n \log n \log V)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005,V=1000000;
int n,cnt,T,sc,st[N],o[N],w[N],a[N],b[N],d[N],dp[N];
int f[N],s[N],p[N],q[N],l[N],rt[N<<2];
vector<pair<int,int> > v[N];
struct node{
    int ls,rs,E;
}t[V*35];
inline int gt(int id,int x){
    return d[id]*x-dp[id];
}
inline void U(int &id,int l,int r,int v){
    if(!id)id=++cnt;int mid=l+r>>1,e=t[id].E;
    if(gt(v,mid)>gt(e,mid))e=v,swap(v,t[id].E);
    if(gt(v,l)>gt(e,l))U(t[id].ls,l,mid,v);
    if(gt(v,r)>gt(e,r))U(t[id].rs,mid+1,r,v);
}
inline int Q(int id,int l,int r,int x){
    if(l==r)return gt(t[id].E,x);int mid=l+r>>1;
    return max(x<=mid?Q(t[id].ls,l,mid,x):Q(t[id].rs,mid+1,r,x),gt(t[id].E,x));
}
inline void U(int id,int l,int r,int x,int v){
    U(rt[id],0,V,v);if(l==r)return;int mid=l+r>>1;
    x<=mid?U(id<<1,l,mid,x,v):U(id<<1|1,mid+1,r,x,v);
}
inline int Q(int id,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r)return Q(rt[id],0,V,k);int mid=l+r>>1,res=-2e18;
    if(x<=mid)res=Q(id<<1,l,mid,x,y,k);if(y>mid)res=max(res,Q(id<<1|1,mid+1,r,x,y,k));
    return res;
}
inline void dfs(int x){
    for(pair<int,int> i:v[x])
        d[i.first]=d[x]+i.second,
        dfs(i.first);
    o[x]=++T;
}
inline void sol(int x){
    U(1,1,n,o[x],x);
    for(pair<int,int> i:v[x]){
        int to=i.first,L=o[to],R=o[w[lower_bound(st+1,st+sc+1,d[to]-l[to])-st]];
        st[++sc]=d[to],w[sc]=to,dp[to]=-Q(1,1,n,L,R,p[to])+d[to]*p[to]+q[to],sol(to),--sc;
    }
}
signed main(){
    cin>>n>>dp[0];dp[0]=2e18,dp[1]=0;
    for(int i=2;i<=n;++i)
        cin>>f[i]>>s[i]>>p[i]>>q[i]>>l[i],
        v[f[i]].push_back({i,s[i]});
    w[sc=1]=1,dfs(1),sol(1);for(int i=2;i<=n;++i)cout<<dp[i]<<'\n';return 0;
}

例题 5

请自行阅读题面。

简单的，我们对数轴加上时间维，于是有了一个平面直角坐标系。每个顾客经过的路径是一个平面上的斜率为 \pm 1 的线段。而保镖只需保证每个单位时间移动距离 \le 1。

可以证明，保镖一定存在一条路径满足其可以拆分为若干斜率为 \pm 1 的路径且答案最大。我们只需考虑这种情况即可。

将平面旋转 45 ^\circ。然后上述所有线段都与坐标轴平行，并将单位长度变为 \sqrt{2}，则 (x,y)\gets (x-y,x+y)。我们将 c_i \gets \dfrac{c_i}{2} 可以抵消掉这步对答案的影响。因为 c_i 一定是偶数所以不需要使用浮点数。

将所有顾客路径的线段延长，这样就有了 \mathcal{O}(n^2) 个交点，我们称这些点为关键点。考虑处理出从每个关键点 (x_i,y_j) 开始可以得到的最大贡献 f_{i,j}。

对于一个保镖而言，它一定会先移动到一个关键点。只是在移动到关键点的过程中可能也存在贡献。此时有两种情况，要么先向上，然后向右保护一个顾客直到关键点，要么先向右，然后向上保护一个顾客直到关键点。

以第一种情况为例，假如我们到达的关键点为 (x_i,y_j)，查询点为 (x,y)，我们会先向上移动至 (x,y_j)，然后陪顾客走过长度为 (x_i-x) 的路。记经过端点 (x_i,y_{j-1}),(x_i,y_j) 的顾客的最大 c_{i,j}。则这种移动的方案的答案为 (x_i-x)c_{i,j}+f_{i,j}。

可以看到，对于每个 (i,j)，我们都有一个 cx+f 状的一次函数。我们查询则是所有满足 x_{i-1} \le x \le x_{i},y_j \ge y 的一次函数的在 (x_i-x) 处的最大点值。

对于每种 x_{i-1} \le x \le x_{i} 的情况单独处理，按 y 排序后依次插入即可。使用李超线段树维护一次函数最值。

第二种情况同理。时间复杂度为 \mathcal{O}((n^2 + q) \log V)。

#include<bits/stdc++.h>
#define int long long
#define B begin()
#define E end()
#define lb lower_bound
#define pb push_back
#define vc vector<int>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,ss=1,s=gc;
    while(!isdigit(s)&&s!='-')s=gc;if(s=='-')ss=-1,s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return ss*x;
}
const int N=5805,M=3000005,V=1e9;
int n,q,cnt,cx,cy,rt,ID;
int x[N],y[N],X[N],Y[N],c[N],F[M],A[N],qx[M],qy[M];
int ans[M],ls[N<<5],rs[N<<5],K[N<<5],vx[N][N],vy[N][N],f[N][N];
vc gx,gy,tx[N],ty[N];
inline int cmpx(int x,int y){return qx[x]>qx[y];}
inline int cmpy(int x,int y){return qy[x]>qy[y];}
inline void chk(int &x,int y){x=x>y?x:y;}
inline int gt(int id,int x){return x*A[id]+F[id];}
inline void U(int &id,int l,int r,int v){
    int mid=l+r>>1;if(!id)id=++cnt;
    if(gt(v,mid)>gt(K[id],mid))swap(v,K[id]);
    if(gt(v,l)>gt(K[id],l))U(ls[id],l,mid,v);
    if(gt(v,r)>gt(K[id],r))U(rs[id],mid+1,r,v);
}
inline int Q(int id,int l,int r,int x){
    if(l==r)return gt(K[id],x);int mid=l+r>>1;
    return max(x<=mid?Q(ls[id],l,mid,x):Q(rs[id],mid+1,r,x),gt(K[id],x));
}
inline void BD(){
    for(int i=1;i<=cnt;++i)ls[i]=rs[i]=K[i]=0;
    rt=ID=cnt=0;
}
signed main(){
    n=rd,q=rd,F[0]=-1e18;
    for(int i=1,t,a,b,x1,x2,y1,y2;i<=n;++i)
        t=rd,a=rd,b=rd,c[i]=rd>>1,
        x1=t,x2=t+abs(a-b),y1=a,y2=b,
        gx.pb(x[i]=x1-y1),gy.pb(y[i]=x1+y1),
        gx.pb(X[i]=x2-y2),gy.pb(Y[i]=x2+y2);
    sort(gx.B,gx.E),gx.erase(unique(gx.B,gx.E),gx.E),cx=gx.size();
    sort(gy.B,gy.E),gy.erase(unique(gy.B,gy.E),gy.E),cy=gy.size();
    for(int i=1;i<=n;++i)
        x[i]=lb(gx.B,gx.E,x[i])-gx.B,X[i]=lb(gx.B,gx.E,X[i])-gx.B,
        y[i]=lb(gy.B,gy.E,y[i])-gy.B,Y[i]=lb(gy.B,gy.E,Y[i])-gy.B;
    for(int i=1,t,a,x1,y1;i<=q;++i)
        t=rd,a=rd,qx[i]=t-a,qy[i]=t+a,
        tx[lb(gx.B,gx.E,qx[i])-gx.B].pb(i),
        ty[lb(gy.B,gy.E,qy[i])-gy.B].pb(i);
    for(int i=1;i<=n;++i){
        for(int j=x[i];j<X[i];++j)chk(vx[j][y[i]],c[i]);
        for(int j=y[i];j<Y[i];++j)chk(vy[x[i]][j],c[i]);
    }
    for(int i=cx-1;i>=0;--i){
        for(int j=cy-1;j>=0;--j){
            if(i<cx-1)chk(f[i][j],f[i+1][j]+vx[i][j]*(gx[i+1]-gx[i]));
            if(j<cy-1)chk(f[i][j],f[i][j+1]+vy[i][j]*(gy[j+1]-gy[j]));
        }
    }
    for(int i=0,k;i<cx;++i){
        sort(tx[i].B,tx[i].E,cmpy),BD(),k=cy-1;
        for(int j:tx[i]){
            while(~k&&gy[k]>=qy[j])
                A[++ID]=i?vx[i-1][k]:0,F[ID]=f[i][k],
                U(rt,0,V,ID),--k;
            chk(ans[j],Q(rt,0,V,gx[i]-qx[j]));
        }
    }
    for(int i=0,k;i<cy;++i){
        sort(ty[i].B,ty[i].E,cmpx),BD(),k=cx-1;
        for(int j:ty[i]){
            while(~k&&gx[k]>=qx[j])
                A[++ID]=i?vy[k][i-1]:0,F[ID]=f[k][i],
                U(rt,0,V,ID),--k;
            chk(ans[j],Q(rt,0,V,gy[i]-qy[j]));
        }
    }
    for(int i=1;i<=q;++i)cout<<ans[i]<<'\n';return 0;
}