dsu：CF1278D Segment Tree

· · 题解

勇者 get！dsu 万岁！

维护最终图是不是一个树显然可以用 dsu 动态加边维护，如果加边的时候左右两个点已经连通那么就直接返回不能，最终数 dsu 里的连通块数量就可以判断是不是树。

考虑暴力扫区间内部点加边的问题出在哪里，如果是会建边的区间显然是应该跑的，这样的区间不会超过 n-1，所以问题出在如果一个区间被完全包含的情况，此时复杂度会爆炸。

考虑怎么规避这种情况，首先注意到小区间不可能包含大区间，所以我们按照区间大小升序排序，然后把区间遍历之后直接用白雪皑皑 trick 用 dsu 删掉端点，于是内部的每个端点都会提供边。

所以做到了线性复杂度，遥遥领先 kdl 的神秘 O(n\log n) 顺利翻盘。

哦是不是顺便拿了个现存题解最优复杂度，并查集善良。

注意并查集不要写混。

#include<bits/stdc++.h>
#define N 500005
#define int long long
using namespace std;
struct fish{
    int l,r,siz;
};
vector<fish>ve;
bool cmp(fish x,fish y){
    return x.siz<y.siz;
}
int fa[N<<1];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int fa2[N];
int find2(int x){
    return x==fa2[x]?x:fa2[x]=find2(fa2[x]);
}
int a[N<<1];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        ve.push_back({l,r,r-l+1});
        a[l]=a[r]=i;
        fa2[i]=i;
    }
    n*=2;
    for(int i=1;i<=n+1;i++)
    fa[i]=i;
    sort(ve.begin(),ve.end(),cmp);
    for(fish i:ve){
        for(int j=find(i.l+1);j<i.r;j=find(j+1)){
            if(find2(a[i.l])==find2(a[j])){
                cout<<"NO";
                return 0;
            }
            fa2[find2(a[i.l])]=find2(a[j]);
        }
        fa[find(i.l)]=find(i.l+1);
        fa[find(i.r)]=find(i.r+1);
    }
    int sum=0;
    for(int i=1;i<=n/2;i++)
    sum+=fa2[i]==i;
    if(sum==1)
    cout<<"YES";
    else cout<<"NO";
    return 0;
}
//「是……是是是的！」橙发女孩咬到舌头了。「请都子教！」
//「噢……」樱发女孩似乎有所感叹。「这就是花花公子的笑容……」
//「请您多指教，四等武官。」紫发女孩露出贼笑。「我们相处的时间肯定不会短才对。」

// 接着，第四个进来的那个绿发少女。
// 昨天在费奥多尔眼前，屁股滑了一下，用储水槽表演过跳水花招的那个女孩。
//「初……初初……初次见面……」

// 跟不上状况的她慌得眼睛稍微乱转，即使如此，她还是设法配合了费奥多尔的演技。
//「请多……指教。」