自动搬运

查看原文

来自洛谷，原作者为

	jerry3128 Astill System

搬运于2025-08-24 22:37:28，当前版本为作者最后更新于2022-04-02 11:15:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：维护动态树上带第二关键字比较的重链剖分。

• 轻重边描述的是重链剖分，虚实边描述的是 LCT。
• 复杂度的描述会形如 （外置信息操作+虚实切换用时+查询）
• 考虑一个比较容易证明的事实，对于一次 link-cut 操作前后的树的链剖形态，一条边轻重切换的代价为一，则总代价不会超过 $\mathcal O(\log n)$ 级别。
• 所以我们考虑用 LCT 的虚实边结构直接维护原树剖的轻重剖分结构。具体的我们直接对 LCT 操作，最后在询问之前将需要从虚实与轻重不匹配的边操作掉就行了。然后这些操作在外映射的一个数据结构上面用于求第 $k$ 大。
• 所以问题现在变为了“如何求到一条链上，应该从实边变成虚边的一条边”。我们考虑一条重边，其指向节点的子树大小应该为最大的点。所以我们靠考虑维护差量 $val=mxgsz-sz_{rs}$ 即最大虚儿子大小减去右儿子大小。考虑 LCT 上一个 splay 只关系到其子结构的信息，所以如果一个 splay 节点不是 splay 根节点，它的信息是不完整的。所以我们转移时需要判定右儿子对左儿子的贡献。记录子树最大的 $val$，判定其是不是正数即可。第二关键字一样的，但是码量大了几倍（
• 考虑换根，你反着维护一套信息就行了。
• 那么现在就维护来看就出现了两种方法。

1. 信息由下向上传递，信息来源由上往下查找。

• 因为我们对一个边的虚实切换仍然要往下找到那个点，而且不用维护信息来源，是小常数的好选，也是我的实现方式。
• 但是信息来源的查找相当于做一个跨越虚边 search 的过程，这需要不少的使用技巧，否则复杂度可能劣化。
• 你可以考虑用 set 记录每个节点虚儿子的链顶，以及其子树信息，在做 search 的时候你 splay 一个链顶然后递归处理实链，由下至上依次做。复杂度 $\mathcal O(m\log^{2}n+m\log^{2}n+m\log n)$
• 或者使用 Top-Tree 的技巧直接优化，这样就没有 set 记录子树信息，并且跨越虚边的信息查找可以直接跳跃，也就是我的实现方法。复杂度 $\mathcal O(m\log^{2}n+m\log n+m\log n)$，发现可以多叉摊一下到 $\mathcal O(m\log n \log_{\omega}n+m\log n + m\omega\log_{\omega}n)$。

2. 信息由下向上传递，信息来源一起上传。

• 这种方法信息维护常数比较大，我不觉得能赶过去。（？
• 你把信息来源压入 $val$，一起上传然后直接在树根检索其 $val$ 直到没有非法 $val$ 停止检索。
• 时间复杂度 $\mathcal O(m\log^{2}n+m\log^{tmp^{(1)}}n+m\log n)$。$(1)$ 无法证明 $tmp=1$ 或 $tmp=2$ 或 $tmp=3$。

关键代码

//ayanami保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
const pair<int,int> zero=make_pair(0,0);
int max(int a,int b,int c){return max(a,max(b,c));}
pair<int,int> max(pair<int,int> a,pair<int,int> b,pair<int,int> c){return max(a,max(b,c));}
int n,m;
pair<int,int> operator -(pair<int,int> a,pair<int,int> b){return make_pair(a.first-b.first,a.second-b.second);}
namespace T{
	int tot,sta[200005];
	struct node{
		int ch[3],fa,pre,suf,rev,mx,sz,ans,vmx,rmx,now;pair<int,int> val,ral,gal;
		void insval(pair<int,int> V,int M){if(val.first<V.first||(val.first==V.first&&(val.second+vmx)<(V.second+M)&&V.second>0))val=V,vmx=M;}
		void insral(pair<int,int> V,int M){if(ral.first<V.first||(ral.first==V.first&&(ral.second+rmx)<(V.second+M)&&V.second>0))ral=V,rmx=M;}
	}v[200005];
	void push_up(int rt){
		if(!rt)return;
		if(rt<=n){
			v[rt].pre=v[rt].ch[0]?v[v[rt].ch[0]].pre:rt;
			v[rt].suf=v[rt].ch[1]?v[v[rt].ch[1]].suf:rt;
			v[rt].mx=max(v[v[rt].ch[0]].mx,v[v[rt].ch[1]].mx,rt);
			v[rt].sz=v[v[rt].ch[0]].sz+v[v[rt].ch[2]].sz+1+v[v[rt].ch[1]].sz;
			
			v[rt].val=v[rt].ral=zero,v[rt].vmx=v[rt].rmx=0;
			v[rt].insval(v[v[rt].ch[1]].val,v[v[rt].ch[1]].vmx);
			v[rt].insval(v[v[rt].ch[2]].ral-make_pair(v[v[rt].ch[1]].sz,v[v[rt].ch[1]].mx),v[v[rt].ch[1]].mx);
			v[rt].insval(v[v[rt].ch[0]].val-make_pair(v[rt].sz-v[v[rt].ch[0]].sz,max(max(rt,v[v[rt].ch[1]].mx)-v[v[rt].ch[0]].vmx,0)),max(v[v[rt].ch[0]].vmx,rt,v[v[rt].ch[1]].mx));
			v[rt].insral(v[v[rt].ch[0]].ral,v[v[rt].ch[0]].rmx);
			v[rt].insral(v[v[rt].ch[2]].ral-make_pair(v[v[rt].ch[0]].sz,v[v[rt].ch[0]].mx),v[v[rt].ch[0]].mx);
			v[rt].insral(v[v[rt].ch[1]].ral-make_pair(v[rt].sz-v[v[rt].ch[1]].sz,max(max(rt,v[v[rt].ch[0]].mx)-v[v[rt].ch[1]].rmx,0)),max(v[v[rt].ch[1]].rmx,rt,v[v[rt].ch[0]].mx));
			
			v[rt].gal=max(v[v[rt].ch[0]].gal,v[v[rt].ch[1]].gal,v[v[rt].ch[2]].val);
			v[rt].ans=v[v[rt].ch[0]].ans^rt^v[v[rt].ch[1]].ans;
		}else{
			v[rt].sz=v[v[rt].ch[0]].sz+v[v[rt].ch[1]].sz+v[v[rt].ch[2]].sz;
			v[rt].ral=max(v[v[rt].ch[0]].ral,v[v[rt].ch[1]].ral,make_pair(v[v[rt].ch[2]].sz,v[v[rt].ch[2]].mx));
			v[rt].val=max(v[v[rt].ch[0]].val,v[v[rt].ch[1]].val,max(v[v[rt].ch[2]].val,v[v[rt].ch[2]].gal));
		}
	}
	int gt;
	int searchm(int x){
		push_down(x);
		if(v[x].ch[2]&&v[x].ral==make_pair(v[v[x].ch[2]].sz,v[v[x].ch[2]].mx))return x;
		if(v[x].ch[0]&&v[x].ral==v[v[x].ch[0]].ral)return searchm(v[x].ch[0]);
		if(v[x].ch[1]&&v[x].ral==v[v[x].ch[1]].ral)return searchm(v[x].ch[1]);
		return 0;
	}
	int searchc(int x){
		push_down(x);
		if(v[x].ch[1]&&v[x].val==v[v[x].ch[1]].val)return searchc(v[x].ch[1]);
		if(v[x].ch[2]&&v[x].val==v[v[x].ch[2]].ral-make_pair(v[v[x].ch[1]].sz,v[v[x].ch[1]].mx))return gt=x,searchm(v[x].ch[2]);
		if(v[x].ch[0]&&v[x].val==v[v[x].ch[0]].val-make_pair(v[x].sz-v[v[x].ch[0]].sz,max(max(x,v[v[x].ch[1]].mx)-v[v[x].ch[0]].vmx,0)))return searchc(v[x].ch[0]);
		return 0;
	}
	int searchg(int x){
		push_down(x);
		if(x<=n){
			if(v[x].gal<=zero)return 0;
			if(v[x].ch[2]&&v[x].gal==v[v[x].ch[2]].val)return searchg(v[x].ch[2]);
			if(v[x].ch[1]&&v[x].gal==v[v[x].ch[1]].gal)return searchg(v[x].ch[1]);
			if(v[x].ch[0]&&v[x].gal==v[v[x].ch[0]].gal)return searchg(v[x].ch[0]);
		}else{
			if(v[x].val<=zero)return 0;
			if(v[x].ch[2]&&v[x].val==v[v[x].ch[2]].val)return searchc(v[x].ch[2]);
			if(v[x].ch[0]&&v[x].val==v[v[x].ch[0]].val)return searchg(v[x].ch[0]);
			if(v[x].ch[1]&&v[x].val==v[v[x].ch[1]].val)return searchg(v[x].ch[1]);
			if(v[x].ch[2]&&v[x].val==v[v[x].ch[2]].gal)return searchg(v[x].ch[2]);
		}
		return 0;
	}
	void solve(int x){int g=0;splay(x);while((v[x].val>zero&&(g=searchc(x)))||(v[x].gal>zero&&(g=searchg(x))))splice(g),pre_push_up(gt),splay(x);}
}