自动搬运

查看原文

来自洛谷，原作者为

	Ch1F4N HN 初三最菜 OIer|| 新的赛季 rp ++

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

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

以下是正文

有一个很好写，只需要使用线段树和队列的做法。

首先对横坐标扫描线，我们需要支持加删线段以及合并有交线段的编号。

考虑使用线段树来维护，注意到两个线段有交当且仅当两个线段在线段树上拆出来的节点中存在祖先后代关系，具体证明可以考虑用线段树拆线段相交的部分。

也就是我们需要做的是加入一条线段拆出的节点时，将这些点祖先和子树中还存在的其他线段拆出的节点编号合并。

处理与祖先的合并是简单的，因为暴力即可。

处理儿子的合并考虑使用懒标记，我们在拆出的节点上打一个懒标记表示子树内存在的插入时间早于 $x$ 的线段编号会与某个编号产生一次合并，我们不去下传标记，而是在撤销一条线段的时候将这条线段拆出来的点的祖先中的懒标记施加到这条线段上，考虑对线段树上每个节点用一个队列按照限制从紧到松维护所有懒标记，需要施加标记的时候只需要弹出队尾若干标记，然后因为这些标记代表的编号已经被合并，所以最后再把限制最松的懒标记再次加入队列即可。

容易分析到 $O(n \log n)$。

#include<bits/stdc++.h>
#define fir first
#define sec second
using namespace std;
const int maxn = 5e5+114;
int fa[maxn];
int found(int u){
	return fa[u]=(fa[u]==u?u:found(fa[u]));
}
int e[maxn<<3],tim[maxn<<3];
vector< pair<int,int> > tag[maxn<<3];
int merge(int u,int v){
	fa[found(u)]=found(v);
}
void ins(int cur,int lt,int rt,int l,int r,int id,int beg,int end){
	if(rt<l||r<lt) return ;
	if(e[cur]!=-1){
		fa[found(id)]=found(e[cur]);
	}
	if(l<=lt&&rt<=r){
		tag[cur].push_back(make_pair(beg,found(id)));
		if(e[cur]==-1) e[cur]=found(id);
		tim[cur]=max(end,tim[cur]);
		return ;
	}
	int mid=(lt+rt)>>1;
	ins(cur<<1,lt,mid,l,r,id,beg,end);
	ins(cur<<1|1,mid+1,rt,l,r,id,beg,end);
} 
void del(int cur,int lt,int rt,int l,int r,int id,int beg,int end){
	if(rt<l||r<lt) return ;
	if(tag[cur].size()>0){
		int u=tag[cur].back().fir;
		if(beg<=u){
			while(tag[cur].size()>0&&beg<=tag[cur].back().fir){
				fa[found(tag[cur].back().sec)]=found(id);
				tag[cur].pop_back();
			}
			tag[cur].push_back(make_pair(u,found(id)));
		}
	}
	if(l<=lt&&rt<=r){
		if(tim[cur]==end) e[cur]=-1;
		return ;
	}
	int mid=(lt+rt)>>1;
	del(cur<<1,lt,mid,l,r,id,beg,end);
	del(cur<<1|1,mid+1,rt,l,r,id,beg,end);
}
pair<int,int> opt[maxn<<1];
vector<int> a,b,c,d;
//0-ins 1-del
bool cmp(pair<int,int> x,pair<int,int> y){
	int u=(x.fir==0?a[x.sec]:b[x.sec]);
	int v=(y.fir==0?a[y.sec]:b[y.sec]);
	return (u!=v)?(u<v):(x.fir<y.fir);
}
vector<int> find_union(int n, vector<int> A, vector<int> B, vector<int> C, vector<int> D){
	swap(B,C);
	for(int i=0;i<n;i++) fa[i]=i;
	for(int i=0;i<n;i++) A[i]+=1e9,B[i]+=1e9,C[i]+=1e9,D[i]+=1e9;
	a=A,b=B,c=C,d=D;
	for(int i=0;i<(maxn<<3);i++) e[i]=-1;
	vector<int> vec;
	for(int i=0;i<n;i++) vec.push_back(c[i]),vec.push_back(d[i]);
	sort(vec.begin(),vec.end());
	for(int i=0;i<n;i++){
		int l=0,r=2*n;
		while(l+1<r){
			int mid=(l+r)>>1;
			if(vec[mid]<=c[i]) l=mid;
			else r=mid; 
		} 
		c[i]=l;
		l=0,r=2*n;
		while(l+1<r){
			int mid=(l+r)>>1;
			if(vec[mid]<=d[i]) l=mid;
			else r=mid; 
		} 
		d[i]=l;
	}
	for(int i=0;i<n;i++){
		opt[i*2]=make_pair(0,i);
		opt[i*2+1]=make_pair(1,i);
	}
	sort(opt,opt+2*n,cmp);
	for(int i=0;i<2*n;i++){
		if(opt[i].fir==0) ins(1,0,1e6,c[opt[i].sec],d[opt[i].sec],opt[i].sec,a[opt[i].sec],b[opt[i].sec]);
		else del(1,0,1e6,c[opt[i].sec],d[opt[i].sec],opt[i].sec,a[opt[i].sec],b[opt[i].sec]);
	}
	vector<int> lsh,res;
	lsh.resize(n);
	res.resize(n);
	int t=0;
	for(int i=0;i<n;i++){
		res[i]=(lsh[found(i)]==0?++t:lsh[found(i)]);
		lsh[found(i)]=res[i]; 
	}
	for(int i=0;i<n;i++) res[i]--;
	return res;
}