【树链剖分&李超线段树】【 [SDOI2016]游戏】【题解】

前置知识：

[SDOI2016]游戏

题目大意

给定一棵树，每次在一条链上加入一条以深度为下标的线段，每次查询一条链上的最小值。

Solution

加入线段和查询最值，可以想到用线段树维护，又因为是对树上的链进行操作，而查询的信息不满足差分性质，所以考虑树链剖分+李超线段树。
但是本题中，线段在点x的值不再是\(k*x+b\),而是\(k*dis[x]+b\),也就是说，我们插入的可能不再是条线段，而是一条可能有多个拐点的折线，这仍然能用李超树维护吗？
事实上，只要保证插入的两个函数最多只有一个交点（或是重合），就能用李超树维护。插入的折线相当于是将横坐标离散化后的线段，所以任意两条线段最多只有一个交点（如果不重合），满足李超树的适用范围。
而且本题需要区间查询最小值，只需对李超树的每个节点保存一个最小值，在当前节点区间的范围在查询范围之内时，直接返回最小值，不在往下递归。但需要注意的是，由于李超树基于标记永久化实现，在查询过程中遇到的点依然需要累积到答案中去。
复杂度：O(\(Nlog^3N\))

Code

#include
using namespace std;
#define int long long
inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) {putchar('-');x=~(x-1);}
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1e5+100,inf=123456789123456789;
int n,m,d[N],top[N],siz[N],hs[N],dfn[N],fa[N],id[N];
struct node{
	int l,r,k,b,minn;
}t[N<<2];
struct E{
	int nxt,to,w;
}e[N<<1];
int cnt,hd[N],tot;
void adde(int x,int y,int z)
{
	e[++cnt].nxt=hd[x];
	e[cnt].w=z;
	e[cnt].to=y;
	hd[x]=cnt;
}
void dfs1(int x)
{
	siz[x]=1;
	for(int i=hd[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(y==fa[x]) continue;
		fa[y]=x;
		d[y]=d[x]+e[i].w;
		dfs1(y);
		siz[x]+=siz[y];
		if(siz[y]>siz[hs[x]]) hs[x]=y;
	}
}
void dfs2(int x)
{
	dfn[x]=++tot;
	id[tot]=x;
	if(hs[x]){
		top[hs[x]]=top[x];
		dfs2(hs[x]);
	}
	for(int i=hd[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(dfn[y]) continue;
		top[y]=y;
		dfs2(y);
	}
}
void build(int x,int l,int r)
{
	t[x].l=l,t[x].r=r;
	t[x].k=0;t[x].b=inf;
	t[x].minn=inf;
	if(l==r) return;
	int mid=l+r>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void pushup(int x)
{
	t[x].minn=min(t[x].minn,min(t[x<<1].minn,t[x<<1|1].minn));
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(d[top[x]]=l&&t[x].r<=r)
	{
		return t[x].minn;
	}
	int res=min(t[x].k*max(d[id[l]],d[id[t[x].l]])+t[x].b,t[x].k*min(d[id[r]],d[id[t[x].r]])+t[x].b);
	int mid=t[x].l+t[x].r>>1;
	if(l<=mid) res=min(res,query(x<<1,l,r));
	if(r>mid) res=min(res,query(x<<1|1,l,r));
	return res;
}
int ask(int x,int y)
{
	int g=lca(x,y);
	int res=inf;
	while(top[x]!=top[g]) res=min(res,query(1,dfn[top[x]],dfn[x])),x=fa[top[x]];
	while(top[y]!=top[g]) res=min(res,query(1,dfn[top[y]],dfn[y])),y=fa[top[y]];
	if(dfn[x]>1;
	if(t[x].l>=l&&t[x].r<=r)
	{
		int y[2][2];
		y[0][0]=t[x].k*d[id[t[x].l]]+t[x].b;
		y[0][1]=t[x].k*d[id[t[x].r]]+t[x].b;
		y[1][0]=k*d[id[t[x].l]]+b;
		y[1][1]=k*d[id[t[x].r]]+b;
		if(y[1][0]>=y[0][0]&&y[1][1]>=y[0][1])return;
		if(y[1][0]<=y[0][0]&&y[1][1]<=y[0][1]){
			update(x,k,b,min(y[1][0],y[1][1]));
			return;
		}
		int valmid[2]={t[x].k*d[id[mid]]+t[x].b,k*d[id[mid]]+b};
		if(valmid[0]<=valmid[1])
		{
			if(y[0][0]<=y[1][0]) change(x<<1|1,l,r,k,b);
			else change(x<<1,l,r,k,b);
		}
		else
		{
			if(y[0][0]<=y[1][0]) change(x<<1,l,r,t[x].k,t[x].b),update(x,k,b,min(y[1][1],y[1][0]));
			else change(x<<1|1,l,r,t[x].k,t[x].b),update(x,k,b,min(y[1][1],y[1][0]));
		}
		pushup(x);
		return;
	}
	if(l<=mid) change(x<<1,l,r,k,b);
	if(r>mid) change(x<<1|1,l,r,k,b);
	pushup(x);
}
void add(int x,int y,int k,int b)
{
	int g=lca(x,y),dis=d[x];
	while(top[x]!=top[g])
	{
		change(1,dfn[top[x]],dfn[x],-k,b+k*dis);
		x=fa[top[x]];
	}
	while(top[y]!=top[g])
	{
		change(1,dfn[top[y]],dfn[y],k,b+k*(dis-2*d[g]));
		y=fa[top[y]];
	}
	if(dfn[x]