自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:32:24，当前版本为作者最后更新于2021-08-28 16:11:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

常见优化建图技巧

先考虑如何优化题目中给出的建图方式。

首先显然只可能水平线段和竖直线段相交。

考虑对于一个水平线段，如何求出和它相交的竖直线段。

对于每个竖直线段的端点 $y$ 坐标，和水平线段的 $y$ 坐标，从小到大排序。在上端点处加入竖直线段，下端点处删除。用线段树维护所有加入的竖直线段的 $x$ 坐标，则与某条水平线段相交的竖直线段，位于线段树上的一段区间。

需要维护线段树在不同 $y$ 坐标的版本，可持久化即可。

但是我们并不能直接将主席树的点作为虚点，优化建图，因为有可能一些虚点变为割点，导致原图割点减少。

考虑 P5471 [NOI2019] 弹跳 的做法，不直接建出所有边。

观察以下求割点的代码：

void tar(int x){
	int c=0,i=he[x],j;
	for(dfn[x]=low[x]=++id;i;i=ne[i])if(!dfn[j=to[i]]){
		tar(j),++c,low[x]=min(low[x],low[j]);
		if(low[j]==dfn[x])f[x]=1;
	}else low[x]=min(low[x],dfn[j]);
	if(x==r)f[x]=c>1;
}

发现 if 里面的部分只会运行 $O(n)$ 次，可以直接暴力。

但是我们需要知道哪些点会进入 if，即哪些点没有被访问过。

考虑对主席树上每个点维护一个值 $w$，表示这个点子树内没有被访问过的点个数，若这个值大于 $0$ 则继续向下递归，然后 pushup 时更新这个值。访问一个点时找到对应的主席树上的叶子，将这个值改成 $0$。

然后是对已经访问过的点 low[x]=min(low[x],dfn[j])，注意到 $low_x\leq dfn_x$，而对于未访问过的点有 low[x]=min(low[x],low[j])，所以我们可以改为对所有点进行 low[x]=min(low[x],dfn[j])。

需要在主席树上多维护一个值 $m$ 表示 $\min dfn_j$，在访问到一个点时修改即可，容易发现这个值和 $w$ 是同时被修改的，所以可以同时 pushup。

每次向下递归一定是找到一个未访问过的点，或者对经过的所有点更新 $w=0$，所以复杂度均摊是 $O(n\log n)$ 的。

const int N=2e5+3;
int al[N],ar[N],m,rt[N],nd,id,u,v,p[N],low[N],dfn[N];
bool ans[N];
basic_string<int>ad[N],dl[N];
struct T{
	int w,m,l,r;
}t[N*40];
void upd(int&k,int l,int r){//插入和删除
	if(t[++nd]=t[k],k=nd,t[k].w+=v,l==r){
		if(v==1)p[l]=k;
		return;
	}
	int m=l+r>>1;
	u>m?upd(t[k].r,m+1,r):upd(t[k].l,l,m);
}
void up(int k){t[k].w=t[t[k].l].w+t[t[k].r].w,t[k].m=min(t[t[k].l].m,t[t[k].r].m);}
int get(int k,int l,int r){//找点
	if(!t[k].w)return 0;
	if(l==r)return t[k].w=0,t[k].m=++id,l;
	int m=l+r>>1,i;
	if(u<=m)if(i=get(t[k].l,l,m))return up(k),i;
	if(m<v)if(i=get(t[k].r,m+1,r))return up(k),i;
	return up(k),0;
}
int qry(int k,int l,int r){//求最小值
	if(!k||u<=l&&r<=v)return t[k].m;
	int m=l+r>>1;
	if(u<=m)return m<v?min(qry(t[k].l,l,m),qry(t[k].r,m+1,r)):qry(t[k].l,l,m);
	return qry(t[k].r,m+1,r);
}
void tar(int x,bool b){//求割点
	int c=0,i;
	for(dfn[x]=low[x]=id;u=al[x],v=ar[x],i=get(rt[x],1,m);){
		tar(i,0),++c,low[x]=min(low[x],low[i]);
		if(low[i]==dfn[x])ans[x]=1;
	}
	if(u=al[x],v=ar[x],low[x]=min(low[x],qry(rt[x],1,m)),b)ans[x]=c>1;
}
int main(){
	int n,i;
	for(scanf("%d",&n),i=1;i<=n;++i)scanf("%d%d",al+i,ar+i),ad[al[i]+=n]+=i,dl[(ar[i]+=n)+1]+=i;
	for(t[0].m=N,m=n*2;i<=m;++i)scanf("%d%d",al+i,ar+i),ad[al[i]]+=i,dl[ar[i]+1]+=i;
	for(i=1;rt[i]=rt[i-1],i<=m;++i){
		for(auto o:ad[i])u=o,v=1,upd(rt[i],1,m);
		for(auto o:dl[i])u=o,v=-1,upd(rt[i],1,m);
	}
	for(i=1;i<=m;++i)if(!dfn[i])t[p[i]]={0,++id,0,0},tar(i,1);
	for(i=1;i<=n;++i)cout<<ans[i];
	for(puts("");i<=m;++i)cout<<ans[i];
	return 0;
}