自动搬运

查看原文

来自洛谷，原作者为

	NATO 革命尚未成功，同志仍需努力！

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

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

以下是正文

你聪明的，告诉我，你到底改了什么呢？（Boruvka 不是原题最直观但过不去的做法吗）

思路浅析：

看到近乎完全图的生成树问题，立马想到 Boruvka。

边权的绝对值考虑拆开，对 $b$ 做扫描线维护之，下以枚举较大的 $b$ 为例叙述，反之是类似的。

查询与我的边权最小的点即是与我有交的中 $a-b$ 的最小值，现在问题就变成了如何快速找与我有交的点。

标记永久化的做法，感觉很聪明啊（不对啊，这玩意是不是就是线段树区间加查的方法，总之就是十分聪明！）！

考虑线段树的结构，区间询问和修改都被搞到了 $\log n$ 个区间上，而拆出来的询问对修改就要么无交，要么包含或被包含了。

被包含的修改考虑在所有经过经过的节点单独记录它的贡献，查询时调用询问拆出来的节点记录的被包含贡献即可，包含的修改就直接在被修改的节点记录，查询时查所有经过区间即可。

Boruvka 注意到要维护一个不同颜色次小来找不同色最小点。

时间复杂度 $O(n\log^2n)$。

参考代码：

#include<bits/stdc++.h>
#define ll int
#define INF 1147483647
using namespace std;
ll t,n;
ll f[100005];
ll find(ll x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
struct px
{
	ll l,r,a,b;
	bool operator<(const px&bb)const
	{
		return b<bb.b;
	}
}s[100005];
struct xp
{
	ll val,col;
	bool operator<(const xp&b)const
	{
		return val<b.val;
	}
	xp(ll a=INF,ll b=0)
	{
		val=a;col=b;
	}
}minn[100005];
struct nv
{
	xp minn,smin;
};
struct tree
{
	nv mt,up;
}tr[800005];
#define ls(id) id*2
#define rs(id) id*2+1
nv merge(nv a,xp s)
{
	if(a.minn.col==s.col)a.minn=min(a.minn,s);
	else if(s<a.minn)swap(a.minn,a.smin),a.minn=s;
	else a.smin=min(a.smin,s);
	return a;
}
nv mg(nv a,nv b)
{
	a=merge(a,b.minn);
	a=merge(a,b.smin);
	return a;
}
void update(ll id,ll l,ll r,ll ml,ll mr,xp s)
{
	tr[id].up=merge(tr[id].up,s);
	if(ml<=l&&r<=mr)
	{
		
		tr[id].mt=merge(tr[id].mt,s);
		return;
	}
	ll mid=l+r>>1;
	if(ml<=mid)update(ls(id),l,mid,ml,mr,s);
	if(mr>mid)update(rs(id),1+mid,r,ml,mr,s);
}
nv query(ll id,ll l,ll r,ll ml,ll mr)
{
	if(ml<=l&&r<=mr)return tr[id].up;
	ll mid=l+r>>1;
	nv res=tr[id].mt;
	if(ml<=mid)res=mg(res,query(ls(id),l,mid,ml,mr));
	if(mr>mid)res=mg(res,query(rs(id),1+mid,r,ml,mr));
	return res;
}
ll p[200005],tot;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		tot=0;
		for(ll i=1;i<=n;++i)f[i]=i,cin>>s[i].l>>s[i].r>>s[i].a>>s[i].b,p[++tot]=s[i].l,p[++tot]=s[i].r;
		sort(s+1,s+1+n);
		sort(p+1,p+1+tot);
		tot=unique(p+1,p+1+tot)-p-1;
		for(ll i=1;i<=n;++i)
		{
			s[i].l=lower_bound(p+1,p+1+tot,s[i].l)-p;
			s[i].r=lower_bound(p+1,p+1+tot,s[i].r)-p;
		}
		long long res=0;
		ll cot=0;
		while(1)
		{
			ll lc=cot;
			for(ll i=1;i<=4*tot;++i)tr[i].mt.minn=tr[i].mt.smin=tr[i].up.minn=tr[i].up.smin=xp();
			unordered_set<ll>d;
			for(ll i=1;i<=n;++i)minn[i]=xp(),d.insert(find(i));
			for(ll i=1;i<=n;++i)
			{
				nv res=query(1,1,tot,s[i].l,s[i].r);
				res.minn.val+=s[i].a+s[i].b;
				res.smin.val+=s[i].a+s[i].b;
				if(res.minn.col==find(i))minn[find(i)]=min(minn[find(i)],res.smin);
				else minn[find(i)]=min(minn[find(i)],res.minn);
				update(1,1,tot,s[i].l,s[i].r,xp(s[i].a-s[i].b,find(i)));
			}
			for(ll i=1;i<=4*tot;++i)tr[i].mt.minn=tr[i].mt.smin=tr[i].up.minn=tr[i].up.smin=xp();
			for(ll i=n;i;--i)
			{
				nv res=query(1,1,tot,s[i].l,s[i].r);
				res.minn.val+=s[i].a-s[i].b;
				res.smin.val+=s[i].a-s[i].b;
				if(res.minn.col==find(i))minn[find(i)]=min(minn[find(i)],res.smin);
				else minn[find(i)]=min(minn[find(i)],res.minn);
				update(1,1,tot,s[i].l,s[i].r,xp(s[i].a+s[i].b,find(i)));
			}
			for(auto it:d)
			{
				if(minn[it].col==0)continue;
				ll u=find(it),v=find(minn[it].col);
				if(u!=v)
				{
					++cot;res+=minn[it].val;
					f[u]=v;
				}
			}
			if(cot==lc)break;
		}
		if(cot!=n-1)cout<<-1<<'\n';
		else cout<<res<<'\n';
	}
}