你说得对，谁是奶龙呢？

· · 题解

你聪明的，告诉我，你到底改了什么呢？（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';
    }
}