[cf] 795 div2 E.Number of Groups

前言

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