Bzoj 2049 Cave 洞穴勘測

加邊删邊維護聯通性

因為保證中間過程都是一個樹，是以可以LCT來做

其實也可以按時間分治維護一個可撤銷并查集

我寫的是後者

具體見代碼

#include<bits/stdc++.h>
using namespace std;

const int maxn = ;
int arr[maxn];
int fnd(int x){
    return x == arr[x] ? x : arr[x] = fnd(arr[x]);
}
void join(int x,int y){
    x = fnd(x),y = fnd(y);
    if(x != y) arr[x] = y;
}

int st[maxn],ed[maxn],l[maxn],r[maxn];
int m;

bool check(int n,int L,int R){
    for(int i =  ; i <= n ; i ++) arr[i] = i; 
    for(int i =  ; i < m ; i ++){
        if(l[i] <= L && R <= r[i]){
            join(st[i],ed[i]);
        }
    }
    return fnd() == fnd(n);
}

int getans(int n,int x){
    int s = x,e = ;
    int best = -;
    while(s <= e){
        int mid = (s + e) / ;
        if(check(n,x,mid)){
            best = mid;
            s = mid + ;
        }
        else{
            e = mid - ;
        }
    }
    return best == - ?  : best - x + ;
}



int main(){
    int n;
    scanf("%d %d",&n,&m);
    for(int i =  ; i < m ; i ++) 
        scanf("%d %d %d %d",&st[i],&ed[i],&l[i],&r[i]);
    int ans = ;
    for(int i =  ; i < m ; i ++){
        ans = max(ans,getans(n,l[i]));
    }
    if(ans==) puts("Nice work, Dima!");
    else printf("%d\n",ans);
    return ;
}