李超线段树

A.P4097 【模板】李超线段树 / [HEOI2013] Segment

李超线段树是一种支持插入一个定义域为 [l,r][l,r] 的一次函数（即线段，一次函数便于理解）以及求与 x=kx=k 相交的所有线段中交点纵坐标最大的线段的编号的数据结构。

李超线段树的每个区间 [l,r][l,r] 上只存了一条线段，并且这个线段的一次函数定义域 [L,R][L,R] 包含 [l,r][l,r]，意味着这条线段在区间中每一个位置都是合法的。

每次查询的时候我们在线段树上包含 kk 的 log⁡M\log M（MM 为值域）个区间取最优解，复杂度 O(log⁡M)\mathcal{O}(\log M)。

为什么要取 log⁡M\log M 个区间的最优解呢？这就得提到我们怎么选择保留在区间 [l,r][l,r] 上的这一条线段。

首先如果有一条线段严格比另一条更优，即在 ll 和 rr 处值都严格大于另外一条，那么可以结束递归（另一条不可能成为答案）。

如果没有的话，那么说明两条线段一定有交点，我们取区间中点 midmid，在区间 [l,r][l,r] 上保留在 midmid 处值更大的线段，因为在 midmid 处更劣的线段一定在区间的一边是严格劣于另一条的，所以说只需要将这一条递归到另一边的区间，这样就保证了复杂度。然后因为保留在这个区间上的线段是在大部分情况下最优并不是严格最优，所以查询的时候要取最优解。

如果插入直线的话复杂度是 O(log⁡M)\mathcal{O}(\log M) 的，插入线段的话因为要判断区间和线段的一次函数定义域的包含关系所以复杂度是 O(log⁡2M)\mathcal{O}(\log^2 M) 的。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PDI pair<long double,int>
using namespace std;
const int MAXN = 4e4 + 10;
const int MR = 1e5 + 10;
const int mod1 = 39989;
const int mod2 = 1e9;
const long double eps = 1e-9;
const int inf = 2e9;
int num=0;
struct Line{
	long double k,b;
	int mn,mx;
	long double Get(int x){
		if(x<mn||x>mx) return -inf;
		return k*x+b;
	}
}e[MR];
struct Lichao_Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	int id[MAXN<<2];
	void update(int x,int l,int r,int L,int R,int k){
		if(L<=l&&r<=R){
			if(!id[x]){
				id[x]=k;
				return ;
			}
			int mid=(l+r)>>1;
			if(e[k].Get(mid)-e[id[x]].Get(mid)>eps) swap(id[x],k);
			if(e[k].Get(l)-e[id[x]].Get(l)>eps||(e[k].Get(l)==e[id[x]].Get(l)&&k<id[x])) update(ls,l,mid,L,R,k);
			if(e[k].Get(r)-e[id[x]].Get(r)>eps||(e[k].Get(r)==e[id[x]].Get(r)&&k<id[x])) update(rs,mid+1,r,L,R,k);
			return ;
		}
		int mid=(l+r)>>1;
		if(L<=mid) update(ls,l,mid,L,R,k);
		if(R>mid) update(rs,mid+1,r,L,R,k);
	}
	PDI Cmp(PDI p,PDI q){
		if(p.first==q.first) return (p.second<q.second)?p:q;
		else return (p.first-q.first>eps?p:q);
	}
	PDI query(int x,int l,int r,int p){
		PDI res={-inf,0};
		if(id[x]) res={e[id[x]].Get(p),id[x]};
		if(l==r) return res;
		int mid=(l+r)>>1;
		if(p<=mid) res=Cmp(res,query(ls,l,mid,p));
		else res=Cmp(res,query(rs,mid+1,r,p));
		return res;
	}
}T;
int main(){
	int Q,lastans=0;
	scanf("%d",&Q);
	while(Q--){
		int op,x0,y0,x1,y1,k;
		scanf("%d",&op);
		if(!op){
			scanf("%d",&k);
			k=(k+lastans-1)%mod1+1;
			printf("%d\n",lastans=T.query(1,1,mod1,k).second);
		}
		else{
			scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
			x0=(x0+lastans-1)%mod1+1;
			x1=(x1+lastans-1)%mod1+1;
			y0=(y0+lastans-1)%mod2+1;
			y1=(y1+lastans-1)%mod2+1;
			num++;
			if(x0>x1) swap(x0,x1),swap(y0,y1);
			if(x0==x1){
				e[num].k=0,e[num].b=max(y0,y1);
				e[num].mn=e[num].mx=x0;
			}
			else{
				e[num].k=(y1-y0)*1.0/(x1-x0),e[num].b=(y1-e[num].k*x1);
				e[num].mn=x0,e[num].mx=x1;
			}
			T.update(1,1,mod1,e[num].mn,e[num].mx,num);
		}
	}
}
B.[ABC244Ex] Linear Maximization

首先 Aix+Biy→Bi(AiBix+y)A_ix+B_iy\to B_i(\frac{A_i}{B_i}x+y)，然后括号里面这个式子可以转换成一次函数形式 kx+bkx+b：

$$\begin{cases} k_j = X_j\\ b_j = Y_j\\ x_i = \frac{A_i}{B_i}\\ \end{cases} $$

然后问题就转换为插入直线 y=Xjx+Yj(j∈[1,i])y=X_jx+Y_j(j\in[1,i])，问与直线 xi=AiBix_i=\frac{A_i}{B_i} 的交点纵坐标最大值/最小值（Bi>0B_i>0 时求最大值，Bi<0B_i<0 时求最小值），李超线段树维护即可。

然后注意要特判 Bi=0B_i=0 的情况。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 2e5 + 10;
const long double eps = 1e-9;
const int inf = 0x3f3f3f3f;
int Q,cnt=0;
int X[MAXN],Y[MAXN],A[MAXN],B[MAXN];
long double b[MAXN];
ll ans[MAXN];
struct Line{
	int k,b;
	long double Get(long double x){
		return (long double)(k*x+b);
	}
}e[MAXN];
struct Lichao_Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	struct node{
		int l,r;
		int mn,mx;
	}t[MAXN<<2];
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r,t[x].mn=t[x].mx=0;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r); 
	}
	void update_mx(int x,int k){
		if(!t[x].mx){
			t[x].mx=k;
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		if(e[k].Get(b[mid])-e[t[x].mx].Get(b[mid])>eps) swap(t[x].mx,k);
		if(e[k].Get(b[t[x].l])-e[t[x].mx].Get(b[t[x].l])>eps) update_mx(ls,k);
		if(e[k].Get(b[t[x].r])-e[t[x].mx].Get(b[t[x].r])>eps) update_mx(rs,k);
	}
	void update_mn(int x,int k){
		if(!t[x].mn){
			t[x].mn=k;
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		if(e[t[x].mn].Get(b[mid])-e[k].Get(b[mid])>eps) swap(t[x].mn,k);
		if(e[t[x].mn].Get(b[t[x].l])-e[k].Get(b[t[x].l])>eps) update_mn(ls,k);
		if(e[t[x].mn].Get(b[t[x].r])-e[k].Get(b[t[x].r])>eps) update_mn(rs,k);
	}
	int query_mx(int x,int p){
		if(!t[x].mx) return 0;
		int id=t[x].mx;
		if(t[x].l==t[x].r) return id;
		int mid=(t[x].l+t[x].r)>>1,tmp;
		if(p<=mid) tmp=query_mx(ls,p);
		else tmp=query_mx(rs,p);
		if(tmp&&e[tmp].Get(b[p])-e[id].Get(b[p])>eps) id=tmp;
		return id; 
	}
	int query_mn(int x,int p){
		if(!t[x].mn) return 0;
		int id=t[x].mn;
		if(t[x].l==t[x].r) return id;
		int mid=(t[x].l+t[x].r)>>1,tmp;
		if(p<=mid) tmp=query_mn(ls,p);
		else tmp=query_mn(rs,p);
		if(tmp&&e[id].Get(b[p])-e[tmp].Get(b[p])>eps) id=tmp;
		return id; 
	}
}T;
int main(){
	int Q,mnx=inf,mxx=-inf;
	scanf("%d",&Q);
	FL(i,1,Q){
		scanf("%d%d%d%d",&X[i],&Y[i],&A[i],&B[i]);
		mnx=min(mnx,X[i]),mxx=max(mxx,X[i]);
		if(B[i]==0) ans[i]=max(1ll*A[i]*mnx,1ll*A[i]*mxx);
		else b[++cnt]=1.0*A[i]/B[i];
		e[i]={X[i],Y[i]};
	}
	if(!cnt){
		FL(i,1,Q) printf("%lld\n",ans[i]);
		exit(0);
	}
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	T.build(1,1,cnt);
	FL(i,1,Q){
		T.update_mx(1,i);
		T.update_mn(1,i);
		if(B[i]==0) continue;
		int p=lower_bound(b+1,b+cnt+1,(long double)(1.0*A[i]/B[i]))-b;
		int id=(B[i]>0?T.query_mx(1,p):T.query_mn(1,p));
		ans[i]=1ll*A[i]*e[id].k+1ll*B[i]*e[id].b;
	}
	FL(i,1,Q) printf("%lld\n",ans[i]);
}
C.P5504 [JSOI2011] 柠檬

我们令 dpidp_i 表示前 ii 个贝壳可以变出柠檬数量的最大值。

然后我们可以列出转移方程：

dpi=max⁡{dpj−1+val(i,j)}dp_i=\max\{dp_{j-1}+val(i,j)\}

val(i,j)val(i,j) 表示 [i,j][i,j] 段变出柠檬数量的最大值。

然后我们发现 dpidp_i 是单调不减的，那么一个转移是有意义的当且仅当 ai=aja_i=a_j，于是进一步简化转移方程：

$$dp_i=\max_{\begin{subarray}{l} a_i=a_j=k\\ 1\le j\le i \end{subarray}}\{dp_{j-1}+k\times [s_{i,k}-(s_{j,k}-1)]^2\} $$

然后我们开始推式子：

$$dp_i=dp_{j-1}+k\times (s_{i,k})^2+k\times (s_{j,k}-1)^2-2\times k\times s_{i,k}\times (s_{j,k}-1)\\ dp_i-k\times (s_{i,k})^2=-2\times k\times (s_{j,k}-1) \times s_{i,k}+(dp_{j-1}+k\times (s_{j,k}-1)^2) $$

然后我推着推着推成了经典斜率优化形式 bi=yj−kixjb_i=y_j-k_ix_j：

$$\begin{cases} b_i = dp_i-k\times (s_{i,k})^2\\ y_j = dp_{j-1}+k\times (s_{j,k}-1)^2\\ k_i = 2s_{i,k}\\ x_j = k\times (s_{j,k}-1)\\ \end{cases} $$

因为今天学了李超线段树，所以我们尝试用李超线段树维护。

这个式子的右边可以变成 kjxi+bjk_jx_i+b_j 的形式：

$$\begin{cases} b_j = dp_{j-1}+k\times (s_{j,k}-1)^2\\ k_j = -2\times k\times (s_{j,k}-1)\\ x_i = s_{i,k}\\ \end{cases} $$

然后就可以维护了，即求 dpi=max⁡{kjxi+bj}+k×(si,k)2dp_i=\max\{k_jx_i+b_j\}+k\times (s_{i,k})^2。

另：笔者对斜率优化和李超线段树的一些理解：

斜率优化是把关于 jj 的信息作为二维平面上的一个点来维护然后用一条关于 ii 的直线去截它然后求最大截距，

然后李超线段树维护的是把关于 jj 的信息作为一条直线然后求 ii 的信息代入之后的最大的值。

是两个相反的变形方向。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXM = 1e4 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[MAXN],cnt[MAXM];
int rt[MAXM];
ll f[MAXN];
struct Line{
	ll k,b;
	ll Get(int x){
		return (ll)(k*x+b); 
	}
}e[MAXN];
struct Lichao_Segment_Tree{
	#define ls t[x].Ls
	#define rs t[x].Rs
	int tot=0;
	struct node{
		int l,r;
		int id;
		int Ls,Rs;
	}t[MAXN<<4];
	void build(int &x,int l,int r){
		x=++tot;
		t[x].l=l,t[x].r=r,t[x].id=t[x].Ls=t[x].Rs=0;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void update(int x,int k){
		if(!t[x].id){
			t[x].id=k;
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		if(e[k].Get(mid)>e[t[x].id].Get(mid)) swap(t[x].id,k);
		if(e[k].Get(t[x].l)>e[t[x].id].Get(t[x].l)) update(ls,k);
		if(e[k].Get(t[x].r)>e[t[x].id].Get(t[x].r)) update(rs,k);
	}
	ll query(int x,int p){
		if(!t[x].id) return 0;
		ll res=e[t[x].id].Get(p);
		if(t[x].l==t[x].r) return res;
		int mid=(t[x].l+t[x].r)>>1;
		if(p<=mid) res=max(res,query(ls,p));
		else res=max(res,query(rs,p));
		return res;
	}
}T;
int main(){
	scanf("%d",&n);
	FL(i,1,n) scanf("%d",&a[i]),cnt[a[i]]++;
	FL(i,1,10000)
		if(cnt[i]) T.build(rt[i],1,cnt[i]);
	memset(cnt,0,sizeof(cnt));
	FL(i,1,n){
		cnt[a[i]]++;
		e[i].k=-2ll*a[i]*(cnt[a[i]]-1);
		e[i].b=f[i-1]+1ll*a[i]*(cnt[a[i]]-1)*(cnt[a[i]]-1);
		T.update(rt[a[i]],i);
		f[i]=T.query(rt[a[i]],cnt[a[i]])+1ll*a[i]*cnt[a[i]]*cnt[a[i]];
	}
	printf("%lld\n",f[n]);
}
D.P2305 [NOI2014] 购票

初始值 f1=0f_1=0，

fi=min⁡(fj+(di−dj)×pi+qi)f_i=\min(f_j+(d_i-d_j)\times p_i+q_i)，jj 是 ii 的祖先。

$$f_i=d_ip_i+q_i-d_jp_i+f_j\\ f_i-d_ip_i-q_i=-d_jp_i+f_j\\ $$

我们可以把上式化成 kjxi+bjk_jx_i+b_j 的形式：

$$\begin{cases} k_j = -d_j\\ b_j = f_j\\ x_i = p_i\\ \end{cases} $$

因为题目有距离限制要求区间查询所以考虑线段树套可撤销李超线段树。

然后有一个很妙的做法是利用出栈序，也就是每个结点离开 dfs 的顺序。直接在点 ii 及其最远的满足 di−dj≤lid_i-d_j\le l_i 的祖先 jj 的出栈序对应的区间上查询。容易发现区间内不在 ii 和 jj 的路径上的点都未被访问到（可以发现访问到 ii 的时候只访问了 ii 的祖先以及在 ii 前面的兄弟，即只有这些节点有值，然后因为 ii 前面的兄弟的出栈序必定小于 ii 的出栈序所以不会查询到），不会对答案产生贡献。时间复杂度 O(nlog2n)\mathcal{O}(nlog^2n)，空间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。

注：动态开点李超线段树的空间复杂度是 O(n)\mathcal{O}(n)，因为我们每次遇到空点就直接返回，最多只会新建一个节点。

以及还有什么样的问题可以应用出栈序这个trick：将一段具有祖孙关系的点对之间的路径直接映射到了序列上的一段区间，从而将树上问题转化成了序列上的问题。相当树剖的简化版，少了 O(log⁡n)\mathcal{O}(\log n) 的拆分过程，因为只查询祖先栈里面的元素。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll MAXN = 2e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll C = 1e6;
ll n,type;
ll f[MAXN];
ll s[MAXN],p[MAXN],q[MAXN],l[MAXN]; 
ll id[MAXN],idx=0;
ll dep[MAXN];
ll st[MAXN],dis[MAXN],top=0;
vector<ll>G[MAXN];
struct Line{
	ll k,b;
	ll Get(ll x){
		return k*x+b;
	}
}e[MAXN];
ll rt[MAXN<<2];
struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	ll tot=0;
	struct node{
		ll id;
		ll Ls,Rs;
	}t[MAXN*30];
	void update(ll &x,ll l,ll r,ll k){
		if(!x){
			x=++tot,t[x].id=k;
			return ;
		}
		ll mid=(l+r)>>1;
		if(e[k].Get(mid)<e[t[x].id].Get(mid)) swap(t[x].id,k);
		if(e[k].Get(l)<e[t[x].id].Get(l)) update(t[x].Ls,l,mid,k);
		if(e[k].Get(r)<e[t[x].id].Get(r)) update(t[x].Rs,mid+1,r,k);
	}
	ll query(ll x,ll l,ll r,ll p){
		if(!x||!t[x].id) return inf;
		ll res=e[t[x].id].Get(p);
		if(l==r) return res;
		ll mid=(l+r)>>1;
		if(p<=mid) res=min(res,query(t[x].Ls,l,mid,p));
		else res=min(res,query(t[x].Rs,mid+1,r,p));
		return res;
	} 
	void Update(ll x,ll l,ll r,ll p,ll k){
		update(rt[x],0,C,k);
		if(l==r) return ;
		ll mid=(l+r)>>1;
		if(p<=mid) Update(ls,l,mid,p,k);
		else Update(rs,mid+1,r,p,k);
	}
	ll Query(ll x,ll l,ll r,ll L,ll R,ll k){
		if(L<=l&&r<=R) return query(rt[x],0,C,k);
		ll mid=(l+r)>>1;
		if(R<=mid) return Query(ls,l,mid,L,R,k);
		else if(L>mid) return Query(rs,mid+1,r,L,R,k);
		else return min(Query(ls,l,mid,L,R,k),Query(rs,mid+1,r,L,R,k)); 
	} 
}T;
void init(ll u){
	for(ll v:G[u]) init(v);
	id[u]=++idx;
}
void dfs(ll u,ll fa){
	dep[u]=dep[fa]+s[u];
	st[++top]=u,dis[top]=dep[u];
	if(u!=1){
		ll pos=lower_bound(dis+1,dis+top+1,dep[u]-l[u])-dis;
		f[u]=T.Query(1,1,n,id[u],id[st[pos]],p[u])+dep[u]*p[u]+q[u];
	}
	e[u].k=-dep[u],e[u].b=f[u];
	T.Update(1,1,n,id[u],u);
	for(ll v:G[u]) dfs(v,u);
	top--;
}
signed main(){
	scanf("%lld%lld",&n,&type);
	FL(i,2,n){
		ll x;
		scanf("%lld%lld%lld%lld%lld",&x,&s[i],&p[i],&q[i],&l[i]);
		G[x].push_back(i); 
	}
	init(1);
	f[1]=0,dfs(1,0);
	FL(i,2,n) printf("%lld\n",f[i]);
}
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 25ms
  4. Powered by Hydro v4.14.1 Community