学习笔记 李超线段树

写在之前

李超线段树 简称\(LCT\)

正式开始

李超线段树主要用于维护这样一类问题

有两个操作

1.插入一条直线(k,b) \(y=kx+b\)

2.给出一个值\(x\) 求\(x=k\)与这些直线交点中纵坐标的最大值

我们可以使用\(CDQ\)分治或者平衡树维护

但是这里有了一种玄学鬼畜的数据结构 李超线段树

\(TA\)的形状同正常的线段树

但是维护的是区间内的优势线段 也就是覆盖最多的线段

比如说 该区间内覆盖最多的线段就是紫色线段

考虑怎么维护

首先对于当前区间\([le,ri]\)

我们假设已经维护了一条最优线段\(old\)

现在加入一条线段\(new\)

存在四种情况

1.\(k_{new}>k_{old}\)

并且\(x=mid\)时 \(y_{old}>y_{new}\) 这个时候

优势线段依然是\(old\)左区间同样 但是右区间不一定

所以我们使用\(new\)去更新右区间 \((mid,ri]\)

2.\(k_{new}>k_{old}\)

并且\(x=mid\)时 \(y_{old} 这个时候

优势线段更新为\(new\) 右区间同样是

但是左区间不一定

所以我们再使用\(old\)去更新左区间\([le,mid]\)

3.\(k_{new}

并且\(x=mid\)时 \(y_{old} 这个时候

优势线段更新为\(new\) 左区间同样是

但是右区间不一定

所以我们再使用\(old\)去更新左区间\((mid,ri]\)

4.\(k_{new}

并且\(x=mid\)时 \(y_{old}>y_{new}\) 这个时候

优势线段依然是\(old\) 右区间同样是

但是左区间不一定

所以我们使用\(new\)去更新左区间\([le,mid]\)

这就是维护

至于查询的

我们使用到了标记永久化的思想

从上到下 不断比较 逐个取\(max\)

例题

P4254 [JSOI2008]Blue Mary开公司

这是一道板子题

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x7fffffff
#define maxn 50005
#define IL inline
#define M 1008611
#define D double
#define mod 998244353
#define R register
using namespace std;
templateIL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n,ans,cnt,tot;
int tre[M<<2];
D cdy[M],wzy[M];
char key[20];
IL D have(int id,int x){return cdy[id]*(x-1)+wzy[id];}
IL void update(int si,int le,int ri,int id)
{
    if(have(id,le)>have(tre[si],le)&&have(id,ri)>have(tre[si],ri)) {tre[si]=id;return;}
    if(have(id,le)<=have(tre[si],le)&&have(id,ri)<=have(tre[si],ri)) return;
    int mid=(le+ri)>>1;
    if(cdy[tre[si]]have(tre[si],mid)) {update(si<<1,le,mid,tre[si]);tre[si]=id;}
        
        else update(si<<1|1,mid+1,ri,id);
    }
    else
    {
        if(have(id,mid)>have(tre[si],mid)) {update(si<<1|1,mid+1,ri,tre[si]);tre[si]=id;}
        else update(si<<1,le,mid,id);
    }
}
IL D qury(int si,int le,int ri,int pos)
{
    if(le==ri) return have(tre[si],pos);
    int mid=(le+ri)>>1;
    if(pos<=mid) return max(have(tre[si],pos),qury(si<<1,le,mid,pos));
    else return max(have(tre[si],pos),qury(si<<1|1,mid+1,ri,pos));
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    read(n);
    while(n--)
    {
        int x;scanf("%s",key+1);
        if(key[1]=='P')
        {
            ++tot;
            scanf("%lf%lf",&wzy[tot],&cdy[tot]);
            update(1,1,maxn,tot);
        }
        else
        {
            read(x);
            printf("%d\n",(int)(qury(1,1,maxn,x)/100.0));
        }
    }
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

P4655 [CEOI2017]Building Bridges

首先这是一道\(dp\)

\[sum[i]=\sum_{i=1}^n w_i \]

\[dp[i]=min\{dp[j]+sum[i-1]-sum[j]+(h[i]-h[j])^2\}(1≤j

最终的答案就是\(dp[n]\)

拆开之后就是

\(dp[i]=min\{dp[j]+sum[i-1]-sum[j]+h[i]^2-2* h[i]* h[j]+h[j]^2\}\)

那么就是查询\(x=h[i]\)时

线段\(y=kx+b\)

\[k=-2* h[j] \]

\[b=h[j]^2-sum[j]+dp[j] \]

对应的\(y\)的最小值 所以我们可以直接使用李超线段树维护

由于定义域为\([-10^6,10^6]\) 李超线段树又是类似于权值线段树

所以我们需要维护成\([0,2* 10^6]\)

然后就是基本操作了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 1e12
#define N 100008
#define IL inline
#define M 1000611
#define D double
#define maxn 2000008
#define R register
using namespace std;
templateIL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
ll n;
ll num[N],hei[N];
ll sum[N],dp[N];
ll cdy[N],wzy[N],tre[M*20];
IL ll have(ll id,ll x){return cdy[id]*(x-1000000)+wzy[id];}
IL void update(ll si,ll le,ll ri,ll id)
{
    if(have(id,le)=have(tre[si],le)&&have(id,ri)>=have(tre[si],ri)) return;
    ll mid=(le+ri)>>1;
    if(cdy[tre[si]]>1;
//	printf("now at %lld\n",mid);
    if(pos<=mid) return min(have(tre[si],pos),qury(si<<1,le,mid,pos));
    else return min(have(tre[si],pos),qury(si<<1|1,mid+1,ri,pos));
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    read(n);
    for(R ll i=1;i<=n;++i) read(hei[i]);
    for(R ll i=1;i<=n;++i) read(num[i]);
    for(R ll i=1;i<=n;++i) sum[i]=sum[i-1]+num[i];
    cdy[0]=wzy[0]=inf;
    cdy[1]=-2*hei[1];wzy[1]=hei[1]*hei[1]-num[1];
    update(1,0,maxn,1);
    for(R ll i=2;i<=n;++i)
    {
//		printf("now at %lld\n",i);
        ll tmp=qury(1,0,maxn,hei[i]+1000000);
//		puts("now at at at at at at at at at at at at at at at at ");
        dp[i]=tmp+sum[i-1]+hei[i]*hei[i];
        cdy[i]=-2*hei[i];wzy[i]=dp[i]+hei[i]*hei[i]-sum[i];
        update(1,1,maxn,i);
    }
    printf("%lld\n",dp[n]);
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}

P4097 [HEOI2013]Segment

这题不一样 维护的是线段

首先对于区间\([le,ri]\)

只有当\(le=x_0\&\&x_1=ri\)时才可以产生贡献

然后对于\(x_0=x_1\)时 由于不存在斜率 需要特判

由于输出编号 所以我维护的是\(pair<>\)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 1e15
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define eps 1e-5
#define maxn 40000
#define R register
using namespace std;
templateIL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
struct Node
{
	D kx,bx;
}e[N];
int n,tot,ans;
int tre[M];
pair fro[M];
IL D key(int at,int now){return e[now].kx*((D)at)+e[now].bx;}
IL void update(int si,int lenow,int rinow,int le,int ri,int id)
{
	if(le==lenow&&rinow==ri)
	{
		if(key(le,id)>key(le,tre[si])&&key(ri,id)>key(ri,tre[si])) {tre[si]=id;return;}
		if(key(le,id)<=key(le,tre[si])&&key(ri,id)<=key(ri,tre[si])) return;
		int mid=(lenow+rinow)>>1;
		if(e[id].kx>=e[tre[si]].kx)
		{
			if(key(mid,id)>=key(mid,tre[si])) update(si<<1,lenow,mid,le,mid,tre[si]),tre[si]=id;
			else update(si<<1|1,mid+1,rinow,mid+1,ri,id);
		}
		else
		{
			if(key(mid,id)>=key(mid,tre[si])) update(si<<1|1,mid+1,rinow,mid+1,ri,tre[si]),tre[si]=id;
			else update(si<<1,lenow,mid,le,mid,id);
		}
	}
	int mid=(lenow+rinow)>>1;
	if(ri<=mid) update(si<<1,lenow,mid,le,ri,id);
	else if(mid comp(pair cdy,pair wzy)
{
	if(fabs(cdy.first-wzy.first)wzy.second) return wzy;
		else return cdy;
	}
	else
	{
		if(cdy.first>wzy.first) return cdy;
		else return wzy;
	}
}
IL pair qury(int si,int le,int ri,int pos)
{
	if(le==ri) return make_pair(key(le,tre[si]),tre[si]);
	int mid=(le+ri)>>1;
	if(pos<=mid) return comp(make_pair(key(pos,tre[si]),tre[si]),qury(si<<1,le,mid,pos));
	else return comp(make_pair(key(pos,tre[si]),tre[si]),qury(si<<1|1,mid+1,ri,pos));
}
int main()
{
	freopen("lct.in","r",stdin);
	freopen("lct.out","w",stdout);
	read(n);
	for(R int i=1;i<=maxn;++i) fro[i].first=-inf,fro[i].second=0;
	e[0].bx=-inf;
	while(n--)
	{
		int knd;read(knd);
		if(knd==1)
		{
			int ax,ay,bx,by;
			read(ax);read(ay);read(bx);read(by);
			ax=(ax+ans)%39989+1;
			ay=(ay+ans)%1000000000+1;
			bx=(bx+ans)%39989+1;
			by=(by+ans)%1000000000+1;
			++tot;
			if(ax==bx)
			{
//				puts("cdy cdy");
				if(aybx) swap(ax,bx),swap(ay,by);
//				printf("(%d , %d) (%d , %d)\n",ax,ay,bx,by);
				e[tot]=(Node){((D)(by-ay))/((D)(bx-ax)),by-bx*((D)(by-ay))/((D)(bx-ax))};
				update(1,1,maxn,ax,bx,tot);
			}
		}
		else
		{
			int x;read(x);x=(x+ans)%39989+1;
			pair tmp=qury(1,1,maxn,x);
			if(tmp.first==-inf&&fro[x].first==-inf) ans=0,puts("0");
			else
			{
				if(fabs(tmp.first-fro[x].first)fro[x].first) printf("%d\n",ans=tmp.second);
					else printf("%d\n",ans=fro[x].second); 
				}
			}
		}
	}
	fclose(stdin);
	fclose(stdout);
    return 0;
}

\(leige\) ：省选考这玩意我当场吃**

HEOI 2019 RP++

学习笔记

相关

Git--学习笔记（三）远程仓库克隆到本地

[学习笔记] 整数规划之割平面法 How and why?

计网学习笔记(5) - 物理层与媒介

selenium python学习笔记之八 窗口截图、验证码处理

AntDesign vue学习笔记（三）嵌套路由使用

vue学习笔记（一）--来源尚硅谷

【学习笔记】TSlib校准原理

Go语言核心36讲（Go语言实战与应用六）--学习笔记

docker 学习笔记-7

SpringMVC学习笔记

Spring 学习笔记

[机器学习笔记(一)] TensorFLow安装

标签