自动搬运

查看原文

来自洛谷，原作者为

	juju527 **

搬运于2025-08-24 22:26:52，当前版本为作者最后更新于2022-07-08 22:09:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

给出一个分治做法。

$\texttt{Solution}$

在 dfn 序上考虑，点 $x$ 的子树补形如整个区间扣掉 $[dfn_x,dfn_x+siz_x-1]$，考虑直接分治。

一个分治区间 $[l,r]$，处理所有 $[dfn_x,dfn_x+siz_x-1]$ 完全包含于 $[l,r]$ 的询问，且已经加入了 $[1,l-1],[r+1,n]$ 的全部信息。

考虑每一层分治处理完所有跨过区间中点 $mid$ 的询问：由于子树区间只有包含关系，所有越过 $mid$ 的区间存在偏序关系，我们增量加入信息即可。

未跨过 $mid$ 的询问直接向下递归。

对于分治的每一层，显然处理跨过区间中点 $mid$ 的询问时进行的加入信息操作为 $O(n)$，则总加入次数为 $O(n\log n)$。

给出核心代码：

void solve(vec p,int l,int r,int d){
	if(!p.size())return ;
	if(l==r){printf("=%d",rdfn[l]);return ;}
	int mid=l+((r-l)>>1);
	vec lt,rt;lt.clear();rt.clear();
	int lp=l-1,rp=r+1;
	for(auto x:p){
		if(R[x]<=mid)lt.eb(x);
		else if(x>mid)rt.eb(x);
		else{
			while(lp<x-1)trans(rdfn[++lp]);
			while(rp>R[x]+1)trans(rdfn[--rp]);
			printf("=%d",rdfn[x]);
		}
	}
	for(int i=lp;i>=l;i--)printf("-");
	for(int i=rp;i<=r;i++)printf("-");
	for(int i=mid+1;i<=r;i++)trans(rdfn[i]);
	solve(lt,l,mid,d+1);
	for(int i=mid+1;i<=r;i++)printf("-");
	for(int i=l;i<=mid;i++)trans(rdfn[i]);
	solve(rt,mid+1,r,d+1);
	for(int i=l;i<=mid;i++)printf("-");
	return ;
}