自动搬运

查看原文

来自洛谷，原作者为

	Reunite Wish us good luck.

搬运于2025-08-24 23:06:16，当前版本为作者最后更新于2024-11-28 20:30:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

无聊的 Boruvka 模板题。

显然考虑 Boruvka，现在仅需考虑一轮内的情况。转化为，每个点有颜色 $bl_i$ 和点权 $a_i$，我们希望求出每种颜色最小的异色边。

边是区间的形式，考虑线段树，容易发现我们的要求仅是不与某个颜色相同，那只要维护最小和次小，并保证颜色不同就一定能取到最优了。边显然有两种形式，一个是作为给出三元组起点连到区间内，一个是被上面这种连。只需要写一个线段树支持区间合并查询，再写一个线段树支持区间修改单点查询即可。封装一下可以合并到一起。

每轮复杂度 $O(n\log n)$，而每次至少使连通块数减半，复杂度为 $O(n\log^2 n)$。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
#define inf 1000000000
using namespace std;

int n,m;
int a[100005];
int bl[100005];
int fa[100005];
int vl[100005];
int to[100005];
vector <pair <int,int>> g[100005];
struct Edge{int u,v,w;}e[400005];
struct node{int mn1,mn2,co1,co2;};
node t[400005];
node tg[400005];
node bt[100005];

inline void in(int &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

node operator + (node p,node q){
	pair <int,int> a[5];
	a[1]={p.mn1,p.co1};
	a[2]={q.mn1,q.co1};
	a[3]={p.mn2,p.co2};
	a[4]={q.mn2,q.co2};
	sort(a+1,a+1+4);
	node tmp;
	tmp.mn1=a[1].first,tmp.co1=a[1].second;
	if(a[2].second!=a[1].second){
		tmp.mn2=a[2].first,tmp.co2=a[2].second;
		return tmp;
	}
	if(a[3].second!=a[1].second){
		tmp.mn2=a[3].first,tmp.co2=a[3].second;
		return tmp;
	}
	if(a[4].second!=a[1].second){
		tmp.mn2=a[4].first,tmp.co2=a[4].second;
		return tmp;
	}
	tmp.mn2=inf,tmp.co2=0;
	return tmp;
}

inline void build(int u,int l,int r){
	tg[u]={inf,inf,0,0};
	if(l==r){t[u]={a[l],inf,bl[l],0};return ;}
	int mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	t[u]=t[u<<1]+t[u<<1|1];
	return ;
}

inline node qry(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R) return t[u];
	int mid=(l+r)>>1;
	if(L>mid) return qry(u<<1|1,mid+1,r,L,R);
	if(R<=mid) return qry(u<<1,l,mid,L,R);
	return qry(u<<1,l,mid,L,R)+qry(u<<1|1,mid+1,r,L,R);
}

inline void upd(int u,int l,int r,int L,int R,node x){
	if(L<=l&&r<=R){tg[u]=tg[u]+x;return ;}
	tg[u<<1]=tg[u<<1]+tg[u];
	tg[u<<1|1]=tg[u<<1|1]+tg[u];
	int mid=(l+r)>>1;
	if(L<=mid) upd(u<<1,l,mid,L,R,x);
	if(R>mid) upd(u<<1|1,mid+1,r,L,R,x);
	return ;
}

inline node qry(int u,int l,int r,int k){
	if(l==r) return tg[u];
	tg[u<<1]=tg[u<<1]+tg[u];
	tg[u<<1|1]=tg[u<<1|1]+tg[u];
	int mid=(l+r)>>1;
	if(k<=mid) return qry(u<<1,l,mid,k);
	else return qry(u<<1|1,mid+1,r,k);
}

inline int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}

int main(){
	in(n),in(m);
	for(int i=1;i<=n;i++) in(a[i]),fa[i]=bl[i]=i;
	while(m--){
		int u,l,r;
		in(u),in(l),in(r);
		g[u].push_back({l,r});
	}
	ll s=0;
	while(1){
		bool ok=1;
		for(int i=1;i<=n;i++) ok&=(Find(i)==Find(1));
		if(ok) break;
		for(int i=1;i<=n;i++) bl[i]=Find(i),bt[i]={inf,inf,0,0},vl[i]=1e9;
		build(1,1,n);
		int m=0;
		for(int i=1;i<=n;i++){
			node tmp={inf,inf,0,0};
			for(auto tt:g[i]){
				tmp=tmp+qry(1,1,n,tt.first,tt.second);
				upd(1,1,n,tt.first,tt.second,{a[i],inf,bl[i],0});
			}
			if(tmp.co1!=bl[i]&&tmp.co1){
				if(vl[bl[i]]>tmp.mn1+a[i]) vl[bl[i]]=tmp.mn1+a[i],to[bl[i]]=tmp.co1;
			}
			if(tmp.co2!=bl[i]&&tmp.co2){
				if(vl[bl[i]]>tmp.mn2+a[i]) vl[bl[i]]=tmp.mn2+a[i],to[bl[i]]=tmp.co2;
			}
		}
		for(int i=1;i<=n;i++){
			auto tmp=qry(1,1,n,i);
			tmp.mn1+=a[i],tmp.mn2+=a[i];
			bt[bl[i]]=bt[bl[i]]+tmp;
		}
		for(int i=1;i<=n;i++){
			if(Find(i)==i){
				if(bt[i].co1!=i&&bt[i].co1){
					if(vl[i]>bt[i].mn1) vl[i]=bt[i].mn1,to[i]=bt[i].co1;
				}
				if(bt[i].co2!=i&&bt[i].co2){
					if(vl[i]>bt[i].mn2) vl[i]=bt[i].mn2,to[i]=bt[i].co2;
				}
				e[++m]={i,to[i],vl[i]};
			}
		}
		sort(e+1,e+1+m,[](Edge p,Edge q){return p.w<q.w;});
		for(int i=1;i<=m;i++){
			int u=Find(e[i].u),v=Find(e[i].v);
			if(u!=v) fa[u]=v,s+=e[i].w;
		}
	}
	printf("%lld\n",s);

	return 0;
}