luoguP4069 [SDOI2016]游戏

题意

显然树剖套李超树。

考虑怎么算函数值：

设\((x,y)\)的\(lca\)为\(z\)，我们插一条斜率为\(k\)，截距为\(b\)的线段。

\((x,z)\)上的点\(u\)：

\(f(u)=k*(dis[x]-dis[u])+b=-k*dis[u]+(k*dis[x]+b)\)

所以对这条路径插入斜率为\(-k\)，截距为\(k*dis[x]+b\)的线段

\((y,z)\)上的点\(u\)：

\(f(u)=k*(dis[y]+dis[u]-2*dis[z])+b=k*dis[u]+k*(dis[y]-2*dis[z])+b\)

同理

code:

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define ls(p) (p<<1)

#define rs(p) (p<<1|1)

#define minn(p)(seg[p].minn)

#define minid(p) (seg[p].minid)

const int maxn=100010;

const int inf=123456789123456789ll;

int n,m,cnt,tim;

int head[maxn],dep[maxn],dfn[maxn],pos[maxn],size[maxn],son[maxn],pre[maxn],top[maxn],dis[maxn];

struct edge{int to,nxt,dis;}e[maxn<<1];

struct Line

{

	int k,b;

	inline int calc(int x){return k*x+b;}

};

struct Seg{int minn;Line minid;}seg[maxn<<2];

inline int read()

{

	char c=getchar();int res=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();

	return res*f;

}

inline void add(int u,int v,int w)

{

	e[++cnt].nxt=head[u];

	head[u]=cnt;

	e[cnt].to=v;

	e[cnt].dis=w;

}

void dfs1(int x,int fa)

{

	pre[x]=fa;dep[x]=dep[fa]+1;size[x]=1;

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		if(y==fa)continue;

		dis[y]=dis[x]+e[i].dis;

		dfs1(y,x);size[x]+=size[y];

		if(size[son[x]]<size[y])son[x]=y;

	}

}

void dfs2(int x,int tp)

{

	top[x]=tp;dfn[x]=++tim;pos[tim]=x;

	if(son[x])dfs2(son[x],tp);

	for(int i=head[x];i;i=e[i].nxt)

	{

		int y=e[i].to;

		if(y==pre[x]||y==son[x])continue;

		dfs2(y,y);

	}

}

inline int lca(int x,int y)

{

	while(top[x]!=top[y])

	{

		if(dep[top[x]]<dep[top[y]])swap(x,y);

		x=pre[top[x]];

	}

	if(dep[x]>dep[y])swap(x,y);

	return x;

}

inline void up(int p){minn(p)=min(minn(p),min(minn(ls(p)),minn(rs(p))));}

void build(int p,int l,int r)

{

	minn(p)=inf;minid(p)=(Line){0,inf};

	if(l==r)return;

	int mid=(l+r)>>1;

	build(ls(p),l,mid);build(rs(p),mid+1,r);

}

inline void move(int p,int l,int r,Line id)

{

	int nowl=minid(p).calc(dis[pos[l]]),nowr=minid(p).calc(dis[pos[r]]);

	int tmpl=id.calc(dis[pos[l]]),tmpr=id.calc(dis[pos[r]]);

	if(nowl<=tmpl&&nowr<=tmpr)return;

	if(nowl>=tmpl&&nowr>=tmpr)

	{

		minid(p)=id;minn(p)=min(minn(p),min(tmpl,tmpr));

		return;

	}

	double point=1.0*(minid(p).b-id.b)/(1.0*(id.k-minid(p).k));

	int mid=(l+r)>>1;

	if(tmpl>nowl)

	{

		if(point<=(double)dis[pos[mid]])move(ls(p),l,mid,minid(p)),minid(p)=id;

		else move(rs(p),mid+1,r,id);

	}

	else

	{

		if(point<=(double)dis[pos[mid]])move(ls(p),l,mid,id);

		else move(rs(p),mid+1,r,minid(p)),minid(p)=id;

	}

	minn(p)=min(minn(p),min(tmpl,tmpr));

	up(p);

}

void change(int p,int l,int r,int ql,int qr,Line id)

{

	if(l>=ql&&r<=qr){move(p,l,r,id);return;}

	int mid=(l+r)>>1;

	if(ql<=mid)change(ls(p),l,mid,ql,qr,id);

	if(qr>mid)change(rs(p),mid+1,r,ql,qr,id);

	up(p);

}

int query(int p,int l,int r,int ql,int qr)

{

	if(l>=ql&&r<=qr)return minn(p);

	int mid=(l+r)>>1,res=min(minid(p).calc(dis[pos[max(l,ql)]]),minid(p).calc(dis[pos[min(r,qr)]]));

	if(ql<=mid)res=min(res,query(ls(p),l,mid,ql,qr));

	if(qr>mid)res=min(res,query(rs(p),mid+1,r,ql,qr));

	return res;

}

inline void trchange(int x,int y,int k,int b)

{

	while(top[x]!=top[y])

	{

		change(1,1,n,dfn[top[x]],dfn[x],(Line){k,b});

		x=pre[top[x]];

	}

	change(1,1,n,dfn[y],dfn[x],(Line){k,b});

}

inline void trsolve(int x,int y,int k,int b)

{

	int z=lca(x,y);

	trchange(x,z,-k,k*dis[x]+b);

	trchange(y,z,k,k*(dis[x]-(dis[z]<<1))+b);

}

inline int trquery(int x,int y)

{

	int res=inf;

	while(top[x]!=top[y])

	{

		if(dep[top[x]]<dep[top[y]])swap(x,y);

		res=min(res,query(1,1,n,dfn[top[x]],dfn[x]));

		x=pre[top[x]];

	}

	if(dep[x]>dep[y])swap(x,y);

	res=min(res,query(1,1,n,dfn[x],dfn[y]));

	return res;

}

signed main()

{

	//freopen("test.in","r",stdin);

	//freopen("test.out","w",stdout);

	n=read(),m=read();

	for(int i=1;i<n;i++)

	{

		int u=read(),v=read(),w=read();

		add(u,v,w),add(v,u,w);

	}

	dfs1(1,0),dfs2(1,1);

	build(1,1,n);

	for(int i=1;i<=m;i++)

	{

		int op=read(),x=read(),y=read(),k,b;

		if(op==1)k=read(),b=read(),trsolve(x,y,k,b);

		else printf("%lld\n",trquery(x,y));

	}

	return 0;

}

巴特西

luoguP4069 [SDOI2016]游戏

题意

最新文章

热门文章