CF1981E

感觉这题比赛时反应出来的简单。

首先容易发现一个性质：如果有 $a_i<a_j,a_j<a_k$ 且 $i,j,k$ 两两连边，那么 $(i,k)$ 这条边是完全没用的，因为会直接被 $(i,j),(j,k)$ 代替。

这启发我们先按照 $a_i$ 升序排序。对于每个区间 $[l_i,r_i]$，我们先看之前有哪些区间 $[l_j,r_j]$ 和这段区间有交。根据上面的性质，我们只用考虑其中 $a_i$ 最大的。也就是说，如果一个区间 $[l_j,r_j]\cup[l_i,r_i]$ 被 $[l_k,r_k]\cup[l_i,r_i]$ 所包含且 $a_k>a_j$，则 $i$ 不会向 $k$ 连边。然后发现这就相当于每次区间覆盖，向区间内出现过的数连边。

根据颜色段均摊，这样的边数是 $O(n)$ 的。最后再跑一遍 Kruskal 即可。

code：

int n,m;
struct node{
	int l,r,x;
}a[N],E[M];
struct CHTree{
	struct node{
		int l,r,k;
		node(int _l=0,int _r=0,int _k=0):l(_l),r(_r),k(_k){}
		il bool operator<(const node &rhs)const{
			return l<rhs.l;
		}
	};
	set<node> st;
	il void init(){
		st.clear();
		st.insert(node(1,n,0));
	}
	il auto split(int p){
		auto it=st.lower_bound(node(p));
		if(it!=st.end()&&it->l==p){
			return it;
		}
		node tmp=*--it;
		st.erase(it);
		st.emplace(tmp.l,p-1,tmp.k);
		return st.emplace(p,tmp.r,tmp.k).fi;
	}
	void assign(int l,int r,int k){
		auto itr=split(r+1),itl=split(l);
		for(auto it=itl;it!=itr;it++){
			if(!(it->k)){
				continue;
			}
			E[++m]=(::node){k,it->k,a[k].x-a[it->k].x};
		}
		st.erase(itl,itr);
		st.emplace(l,r,k);
	}
}T;
struct DSU{
	int fa[N];
	void init(){
		rep(i,1,n){
			fa[i]=i;
		}
	}
	int find(int x){
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	il bool merge(int x,int y){
		x=find(x),y=find(y);
		if(x==y){
			return 0;
		}
		fa[x]=y;
		return 1;
	}
}D;
il bool cmp(node x,node y){
	return x.x<y.x;
}
void Yorushika(){
	scanf("%d",&n),m=0;
	rep(i,1,n){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
	}
	sort(a+1,a+n+1,cmp);
	T.init();
	rep(i,1,n){
		T.assign(a[i].l,a[i].r,i);
	}
	sort(E+1,E+m+1,cmp);
	D.init();
	ll ans=0;int cnt=0;
	rep(i,1,m){
		int u=E[i].l,v=E[i].r;
		if(D.merge(u,v)){
			ans+=E[i].x;
			cnt++;
		}
	}
	printf("%lld\n",cnt<n-1?-1:ans);
}
signed main(){
	int t=1;
		scanf("%d",&t);
	while(t--)
		Yorushika();
}