• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

李超线段树学习笔记

admin

11月 28, 2021

咕咕咕了不知道多久,来写一下吧:

李超线段树,目前我只知道可以用来维护线段的信息,比较受限

主要是维护一些线段(或直线),然后查询以 $x=a$ 的直线切这些线段的纵坐标的最大(小)值

很显然不好直接维护,因为不具有什么单调性之类的,我们考虑依次插入一条线段

对于当前区间( $x in [l,r]$ ):

我们定义 $[l,r]$ 的最优线段是以当 $x=mid$ (  $mid=lfloorfrac{l+r}{2}floor$ )时纵坐标最大的线段

定义左区间为 $[l,mid]$ ,右区间为 $[mid+1,r]$

我们考虑插入的步骤(设插入线段为 $y’=k’x+b’$ ,原最优线段为 $y=kx+b$ ):

1、 当插入一条线段在当前区间时,如果我们发现新线段为该区间的最优线段时,我们就将最优线段变为新线段,改为插入原最优线段

2、 如果插入线段严格劣于最优线段即 $x in [l,r]   y'<y$  时,说明插入此线段起不到任何贡献,直接不用插入了

3、 否则,因为当前需插入线段肯定不是最优线段(如果是,步骤 $1$ 进行了交换),我们看这条线段是否能对左区间,右区间产生贡献,就判断一下 $x=l$ 和 $x=r$ 中哪头 $y’>y$ ,往那边继续插入即可

图?暂且鸽了

我们发现这些操作都可以用线段树维护,直接维护即可

一个小 $ ext{trick}$ :可以大力动态开点,李超线段树由于插入一次顶多会多加一个区间,所以空间严格 $O(n)$ (再也不用怕忘开 $4$ 倍了)

$code$ :

namespace Line_Seg_Tree{

    #define maxn ?//看会插入多少条线段
    #define INF 1000000000000000000

    const int MAXN=?;//看边界需要定多少

    long long k[maxn],b[maxn]={INF};

    inline long long y(int x,int num){
        return k[num]*x+b[num];
    }
    
    int cnt,tot=1,rt,num[maxn],ls[maxn],rs[maxn];

    void add(int &p,int l,int r,int numb){
        if(!p)p=++tot;
        if(l==r){
            if(y(l,numb)<y(l,num[p]))num[p]=numb;
            return;
        }
        int mid=(l+r)>>1;
        if(y(mid,numb)<y(mid,num[p]))swap(num[p],numb);//步骤1
        if(y(l,numb)<y(l,num[p]))add(ls[p],l,mid,numb);//步骤2 和步骤3 一起进行,因为两边都小于就不会进行了
        else if(y(r,numb)<y(r,num[p]))add(rs[p],mid+1,r,numb);
    }

    long long query(int p,int l,int r,int x){
        if(!p)return 1e18;
        if(l==r)return y(x,num[p]);
        int mid=(l+r)>>1;
        if(x<=mid)return min(y(x,num[p]),query(ls[p],l,mid,x));
        else return min(y(x,num[p]),query(rs[p],mid+1,r,x));
    }

    inline void Add(long long K,long long B){
        cnt++,k[cnt]=K,b[cnt]=B;
        add(rt,1,MAXN,cnt);
    }

    inline long long Ask(int x){
        return query(rt,1,MAXN,x);
    }

    #undef maxn
    #undef INF

}

例题: (板子题就不讲了)

[CEOI2017] Building Bridges

很容易列出暴力 $ ext{DP}$ 式(懒得写了)发现可以写成斜率优化一般形式 ( $s_i$ 是前缀和):

$f_i-h_i^2-s_{i-1}= min {-2h_j imes h_i + f_j + h_j^2 -s_j }$

注意这里是用一条直线表达而不是点,发现直接大力李超维护即可:

$code$ :

#include<cstdio>
#include<cctype>

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f?-r:r;
}

template<class T>

inline T min(T a,T b){
	return a<b?a:b;
}

template<class T>

inline void swap(T &a,T &b){
	T c=a;
	a=b;
	b=c;
}

namespace Line_Seg_Tree{

	#define maxn 1001001
	#define INF 1000000000000000000

	const int MAXN=1000000;

    long long k[maxn],b[maxn]={INF};

	inline long long y(int x,int num){
		return k[num]*x+b[num];
	}
	
	int cnt,tot=1,rt,num[maxn],ls[maxn],rs[maxn];

	void add(int &p,int l,int r,int numb){
		if(!p)p=++tot;
        if(l==r){
	        if(y(l,numb)<y(l,num[p]))num[p]=numb;
            return;
        }
		int mid=(l+r)>>1;
		if(y(mid,numb)<y(mid,num[p]))swap(num[p],numb);
		if(y(l,numb)<y(l,num[p]))add(ls[p],l,mid,numb);
		else if(y(r,numb)<y(r,num[p]))add(rs[p],mid+1,r,numb);
	}

	long long query(int p,int l,int r,int x){
		if(!p)return 1e18;
		if(l==r)return y(x,num[p]);
		int mid=(l+r)>>1;
		if(x<=mid)return min(y(x,num[p]),query(ls[p],l,mid,x));
		else return min(y(x,num[p]),query(rs[p],mid+1,r,x));
	}

	inline void Add(long long K,long long B){
		cnt++,k[cnt]=K,b[cnt]=B;
		add(rt,1,MAXN,cnt);
	}

	inline long long Ask(int x){
	    return query(rt,1,MAXN,x);
	}

	#undef maxn
	#undef INF

}

using namespace Line_Seg_Tree;

#define maxn 101101

int n;

long long f[maxn],h[maxn],p[maxn],w[maxn],s[maxn];

int main(){
	n=read<int>();
	for(int i=1;i<=n;i++){
		h[i]=read<long long>();
		p[i]=h[i]*h[i];
	}
	for(int i=1;i<=n;i++){
		w[i]=read<long long>();
		s[i]=s[i-1]+w[i];
	}
	Add(-2ll*h[1],p[1]-s[1]);
	for(int i=2;i<=n;i++){
		f[i]=p[i]+s[i-1]+Ask(h[i]);
		Add(-2ll*h[i],f[i]+p[i]-s[i]);
	}
	printf("%lld
",f[n]);
	return 0;
}

李超树合并:

直接大力线段树合并,一个节点合并完再把要合并的对应点直线在这个区间插入即可

$code$ :

	int merge(int x,int y,int l,int r){
		if(!x||!y)return x|y;
		int mid=(l+r)>>1;
		if(l==r)return Y(mid,num(x))<Y(mid,num(y))?x:y;
		ls(x)=merge(ls(x),ls(y),l,mid);
		rs(x)=merge(rs(x),rs(y),mid+1,r);
		add(x,l,r,num(y));
		return x;
	}

复杂度分析(参考的 $ ext{d}color{red}{ ext{qa2021}}$ $ ext{CF932F}$ 的题解):

线段树深度最大为 $O(log n)$ ,每个线段操作中只会让深度增加,不会减少

所以整个过程为 $O(n log n)$ 的( $n$ 条线段)

例题?就是上面那道,裸的李超树合并

直接贴代码了, $code$ :

#include<cstdio>
#include<cctype>

#define maxn 101101

template<class T>

inline T read(){
	T r=0,f=0;
	char c;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f?-r:r;
}

template<class T>

inline T min(T a,T b){
	return a<b?a:b;
}

template<class T>

inline void swap(T &a,T &b){
	T c=a;
	a=b;
	b=c;
}

struct E{
	int v,nxt;
	E() {}
	E(int v,int nxt):v(v),nxt(nxt) {}
}e[maxn<<1];

int n,s_e,head[maxn],a[maxn],b[maxn],rt[maxn];

long long f[maxn];

inline void a_e(int u,int v){
	e[++s_e]=E(v,head[u]);
	head[u]=s_e;
}

namespace L_S_T{

	#define MAXN 2002002
	#define INF 1000000000000000000

	#define ls(p) tr[p].ls
	#define rs(p) tr[p].rs
	#define num(p) tr[p].num

	const int inf=100000;

    long long k[MAXN],b[MAXN]={INF};

	inline long long Y(int x,int num){
		return k[num]*x+b[num];
	}

	struct TR{
		int ls,rs,num;
	}tr[MAXN];
	
	int cnt,tot=1,num[MAXN],ls[MAXN],rs[MAXN];

	void add(int &p,int l,int r,int numb){
		if(!p)p=++tot;
        if(l==r){
	        if(Y(l,numb)<Y(l,num(p)))num(p)=numb;
            return;
        }
		int mid=(l+r)>>1;
		if(Y(mid,numb)<Y(mid,num(p)))swap(num(p),numb);
		if(Y(l,numb)<Y(l,num(p)))add(ls(p),l,mid,numb);
		else if(Y(r,numb)<Y(r,num(p)))add(rs(p),mid+1,r,numb);
	}

	long long query(int p,int l,int r,int x){
		if(!p)return 1e18;
		if(l==r)return Y(x,num(p));
		int mid=(l+r)>>1;
		if(x<=mid)return min(Y(x,num(p)),query(ls(p),l,mid,x));
		else return min(Y(x,num(p)),query(rs(p),mid+1,r,x));
	}

	int merge(int x,int y,int l,int r){
		if(!x||!y)return x|y;
		int mid=(l+r)>>1;
		if(l==r)return Y(mid,num(x))<Y(mid,num(y))?x:y;
		ls(x)=merge(ls(x),ls(y),l,mid);
		rs(x)=merge(rs(x),rs(y),mid+1,r);
		add(x,l,r,num(y));
		return x;
	}

	inline void Add(int u,long long K,long long B){
		cnt++,k[cnt]=K,b[cnt]=B;
		add(rt[u],-inf,inf,cnt);
	}

	inline long long Ask(int u,int x){
	    return query(rt[u],-inf,inf,x);
	}

	inline void Union(int u,int v){
		rt[u]=merge(rt[u],rt[v],-inf,inf);
	}

	#undef ls
	#undef rs
	#undef num

	#undef INF
	#undef MAXN

}

void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);
		L_S_T::Union(u,v);
	}
	if(!rt[u])f[u]=0;
	else f[u]=L_S_T::Ask(u,a[u]);
	L_S_T::Add(u,b[u],f[u]);
}

int main(){
	n=read<int>();
	for(int i=1;i<=n;i++)
		a[i]=read<int>();
	for(int i=1;i<=n;i++)
		b[i]=read<int>();
	for(int i=1;i<n;i++){
		int u=read<int>();
		int v=read<int>();
		a_e(u,v),a_e(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
		printf("%lld ",f[i]);
	return 0;
}

大概是完结了,有什么再更

发表回复

您的电子邮箱地址不会被公开。