前言
t
a
g
:
tag :
tag:区间问题 合并/分组/覆盖 并查集 ...
传送门 :
思路借鉴 : cup-pyy(Acwing的一个大佬捏)
题意:
给定多个颜色区间
(
c
,
l
,
r
)
(c,l,r)
(c,l,r),满足条件的区间可以进行合并,询问合并之后有多少组
条件如下 :
当两个区间的 颜色 不同的时候,并且两个区间相交的时候那么就可以进行合并
(
c
<
=
1
cn;
//初始化集合
for(int i=1;ia[i].col>>a[i].l>>a[i].r;
op.pb({a[i].l,-i});//左边是入点
op.pb({a[i].r,i});//右边是出点
}
sort(all(op));
set s[2];
for(auto [pos,id] : op){
if(id 1){
merge(id,s[t].begin()->y);
s[t].erase(s[t].begin());
//删除每次都保留最大的
}
if(!s[t].empty()) merge(id,s[t].begin()->y);
}else{//出点 删除
s[a[id].col].erase({a[id].r,id});
}
}
//最终查询有多少个集合
int res = 0 ;
for(int i=1;i
