李超线段树用来维护:给你\(n\)条直线,求出当\(x=a\)时的最大值,支持在线插入.

具体实现:

  我们对于线段树上的每一个节点,记录在\(x=mid\)时的最优线段.

  此时我们即将要插入一条线段为\(A=kx+b\),我们计算一下它在中点处的值为\(val\),\(p\)表示我们记录的线段.

  1. \(val>val_p\),我们比较一下斜率.

     如果\(k>k_{p}\),那么右半区间的答案线段\(A\)一定更优,我们需要寻找一个区间使得\(p\)能成为最优线段.那么我们递归左半区间.

     如果\(k\leq k_{p}\),那么左半区间的答案线段\(A\)一定最优,同理我们递归右半区间.

  2. \(val\leq val_p\).

     如果\(k_{p}> k\),那么右半区间的答案线段\(p\)一定更优,我们需要寻找一个区间使得\(A\)能成为最优线段.那么我们递归左半区间.

     如果\(k_{p}\leq k\),那么左半区间的答案线段\(p\)一定最优,同理我们递归右半区间.

询问\(x=a\)

  我们一路递归下来,对于每个区间的最优线段取一个最大值.

合并

  像线段树合并一样,我们将另一棵树的最优线段插入到这棵树内.

  合并时间和空间复杂度应该为\(O(n\log n)\).

  如果只插入那么空间复杂度应该为\(O(n)\),时间复杂度为\(O(n\log n)\).

代码

struct node {
	int x;
	LL b;
}t[M*20];
struct SEG {
	int Ls[M*20],Rs[M*20];
	LL Calc(node a,LL K) {return a.x*K+a.b;}
	void Insert(int &p,int l,int r,node val) {
		if(!p) {
			p=++Tot;
			t[p]=val;
			return;
		}
		if(l==r) {
			if(Calc(val,C[l])>Calc(t[p],C[l]))t[p]=val;
			return;
		}
		int mid=l+r>>1;
		if(Calc(t[p],C[mid])<Calc(val,C[mid])) {
			if(t[p].x<val.x)Insert(Ls[p],l,mid,t[p]);
			else Insert(Rs[p],mid+1,r,t[p]);
			t[p]=val;
		}else {
			if(t[p].x<val.x)Insert(Rs[p],mid+1,r,val);
			else Insert(Ls[p],l,mid,val);
		}
	}
	LL query(int p,int l,int r,int pos) {
		if(!p)return 0LL;
		if(l==r)return Calc(t[p],C[pos]);
		int mid=l+r>>1;
		LL mx=Calc(t[p],C[pos]);
		if(pos<=mid)return max(mx,query(Ls[p],l,mid,pos));
		return max(mx,query(Rs[p],mid+1,r,pos));
	}
	int Merge(int rt,int lt,int l,int r) {
		if(!rt||!lt)return rt|lt;
		Insert(rt,l,r,t[lt]);
		int mid=l+r>>1;
		Ls[rt]=Merge(Ls[rt],Ls[lt],l,mid);
		Rs[rt]=Merge(Rs[rt],Rs[lt],mid+1,r);
		return rt;
	}
}T;

想法:

  考试时想出了一个写法来替代李超线段树,但是常数更大,内存更大,代码更长,还不好合并两棵树.起码我没有想到.

  因为一条线段取到最优值应该是一个连续的区间\([l,r]\).我大胆猜测如果将这个线段与其他线段的最优值做差,那么这应该是一个有极值的函数.

  那么我们可以用三分转二分的方式,求解出一条线段的\([l,r]\),再将这个二分放在线段树上我们就可以在\(n\log n\)的复杂度插入一个线段了.

代码:

void Down(int p) {
	if(tag[p]==-1)return;
	tag[ls]=tag[p];Ls[ls]=Rs[ls]=tag[p];
	tag[rs]=tag[p];Ls[rs]=Rs[rs]=tag[p];
	tag[p]=-1;
}
void Update(int p,int l,int r,int lx,int rx,int num) {
	if(l==lx&&r==rx) {
		tag[p]=num;
		Ls[p]=Rs[p]=num;
		return;
	}
	Down(p);
	int mid=l+r>>1;
	if(rx<=mid)Update(ls,l,mid,lx,rx,num);
	else if(lx>mid)Update(rs,mid+1,r,lx,rx,num);
	else Update(ls,l,mid,lx,mid,num),Update(rs,mid+1,r,mid+1,rx,num);
	Up(p);
}
LL Calc(int num,int now,int k) {
	return suma[num]-1LL*k*sumb[num]-(suma[now]-1LL*k*sumb[now]);
}
int Query(int p,int l,int r,int pos) {
	if(l==r)return tag[p];
	Down(p);
	int mid=l+r>>1;
	if(pos<=mid)return Query(ls,l,mid,pos);
	return Query(rs,mid+1,r,pos);
}
int Query_L(int p,int l,int r,int pos) {
	if(l==r) {
		if(Calc(pos,tag[p],l-Mx)>=0)return -1;
		return l;
	}
	Down(p);
	int mid=l+r>>1;
	LL lx=Calc(pos,Rs[ls],mid-Mx);
	LL rx=Calc(pos,Ls[rs],mid+1-Mx);
	if(lx<=rx||lx<0)return Query_L(ls,l,mid,pos);
	return Query_L(rs,mid+1,r,pos);
}
int Query_R(int p,int l,int r,int pos) {
	if(l==r)return l;
	Down(p);
	int mid=l+r>>1;
	LL lx=Calc(pos,Rs[ls],mid-Mx);
	LL rx=Calc(pos,Ls[rs],mid+1-Mx);
	if(rx<=lx||rx<0)return Query_R(rs,mid+1,r,pos);
	return Query_R(ls,l,mid,pos);
}
void Update_Mi(int now) {
	int resL=Query_L(1,0,Mxx,now);
	if(resL==-1)return;
	int resR=Query_R(1,0,Mxx,now);
	Update(1,0,Mxx,resL,resR,now);
}