2019 우 커 여름 다 교 훈련소 (제8 차 전) E 익스플로러

제목 링크:https://ac.nowcoder.com/acm/contest/888/E
제목:
n 개의 점 m 변 의 그림 이 있 습 니 다. 각 변 에 숫자 를 통과 할 수 있 는 경계 제한 [l, r] [l, r] [l, r] [l, r] 가 있 습 니 다. 현재 숫자 1 ~ 1e9 는 점 1 에서 점 n 으로 가 야 합 니 다. (한 변 에 숫자 x 가 포함 되 지 않 으 면 숫자 x 는 이 변 을 지나 갈 수 없습니다.)
방법:
분할 치료!!분 치 의 과정 은 매우 대단 하 다 고 할 수 있다. 먼저 모든 경계 l, r 를 이산 화 시 켜 야 한다. 이것 은 모두 알 고 있 을 것 이다. 그러면 1 ~ 1e9 의 구간 을 1 ~ 2e6 로 바 꾸 어 처리 하 는 것 이 매우 편리 할 것 이다.
여기에 앞서 쓴 특수 선분 트 리 의 처리 방법 도 사용 되 었 다.동료 들 과 토론 한 결 과 는 구간 을 이산 화 한 후에 이런 방법 을 비교 할 것 같다 는 것 이다. 어떻게 했 는 지 다시 말 하지 않 겠 다. 왜 tmp [r + 1] - tmp [l] 를 더 해 야 하 는 지 모 르 겠 으 면 직접 여기에 찔러 도 된다.
이 문제 에서 분 산 된 후에 우 리 는 각 변 을 해당 하 는 합 법 적 인 구간 에 저장 해 야 한다. 예 를 들 어 사례 의 변 1 구간 은 1 - 4 1 - 4 1 - 4 1 - 4 이다. 그러면 우 리 는 유사 한 선분 나무의 1 - 4 구간 에 1 이 변 을 저장 해 야 한다.이곳 의 1 - 4 는 분 산 된 위치 1 - 4 1 - 4 1 - 4 입 니 다.
우 리 는 저장 한 후에 직접 분 치 를 시작 합 니 다. dfs 는 이 구간 의 수 를 하 는 것 이 모두 합 법 적 입 니까?내 가 이 구간 에 들 어간 후에 나 는 이미 이 구간 에 어떤 변 을 저장 하 였 는 지 알 아 냈 기 때문에 나 는 직접 이 변 을 찾 아 변 연 결 된 두 점 을 합 쳐 서 점 1 과 점 n 이 하나 에 있 는 지 확인 하고 집합 안에 있 는 지 확인 하면 된다. 없 으 면 계속 [l, m i d] [l, mid] [l, mid] 와 [m i d + 1, r] [mid + 1, r] [mid + 1, r] [mid + 1, r] 로 나 누 어 하면 된다.다 한 후에 집합 을 분리 해 야 한다. 바로 합 병 된 가치 의 fa 를 그들 자신 으로 돌아 가게 하 는 것 이다. (내 가 합병 할 때 아버지의 뿌리 를 찾 았 기 때문에 분할 할 때 자신 이 합 리 적 인 것 이 된다)
여기 서 또 하나의 문 제 는 바로 집합 을 검사 할 때 경로 로 압축 하여 최적화 할 수 없다 는 것 이다. 왜냐하면 당신 이 분할 할 때 뿌리 만 자신 으로 바 꾸 기 때문이다. fin 과정 에서 뿌리 가 아 닌 값 을 변화 시 킬 수 있 기 때문에 돌아 갈 수 없 기 때문에 답 이 틀 릴 수 있다.그러나 경로 가 압축 되 지 않 으 면 바로 T 를 할 수 있 기 때문에 계발 식 합병 이라는 것 을 사용 해 야 합 니 다. sz 배열 을 사용 하여 모든 집합 의 현재 크기 를 기록 해 야 합 니 다. 그러면 경로 수 를 짧 아 질 수 있 습 니 다.
왜 t m p [r + 1] - t m p [l] tmp [r + 1] - tmp [l] tmp [r + 1] - t mp [l] tmp [r + 1] - t mp [l] 인지 모 르 면 위 에 있 는 작은 창의 링크 를 찍 을 수 있 습 니 다. 아래 의 c n t - 1 cnt - 1 cnt - 1 은 마지막 숫자 를 버 리 기 위해 서 입 니 다. 왜 버 려 야 하 는 지 에 대해 서 는 반드시 + 된 오른쪽 구간 이 므 로 의미 가 없 기 때문에 합 법 적 인 구간 에 포함 되 지 않 아 도 됩 니 다.
코드:

#include
#define lson rt<<1
#define rson rt<<1|1
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
using namespace std;
typedef long long ll;
const int maxn=200005;
int tmp[maxn],ct,n,m,fa[maxn],sz[maxn];
int fr[maxn],to[maxn],l[maxn],r[maxn];
vector<int> ve[maxn<<2];
ll ans;
int fin(int x){
    return fa[x]==x?x:fin(fa[x]);
}
void Insert(int l,int r,int rt,int ql,int qr,int v){
    if(ql<=l&&r<=qr){
        ve[rt].push_back(v);
        return ;
    }
    int mid=(l+r)/2;
    if(ql<=mid) Insert(l,mid,lson,ql,qr,v);
    if(qr>mid) Insert(mid+1,r,rson,ql,qr,v);
}
void dfs(int l,int r,int rt){
    vector<int> Back;
    int m=ve[rt].size();
    rep(i,0,m-1){
        int x=ve[rt][i];
        int u=fr[x],v=to[x];
        u=fin(u),v=fin(v);
        if(sz[u]>sz[v]) swap(u,v);
        fa[u]=v,sz[v]+=sz[u],Back.push_back(u);
    }
    int mid=(l+r)/2;
    if(fin(1)==fin(n)) ans=ans+tmp[r+1]-tmp[l];
    else if(l<r){
        dfs(l,mid,lson);
        dfs(mid+1,r,rson);
    }
    m=Back.size();
    for(int i=m-1;i>=0;i--){
        int x=Back[i];
        fa[x]=x;
    }
    Back.clear();
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) fa[i]=i,sz[i]=1;
    int ct=0;
    rep(i,1,m){
        scanf("%d%d%d%d",&fr[i],&to[i],&l[i],&r[i]);
        tmp[++ct]=l[i],tmp[++ct]=r[i]+1;
    }
    sort(tmp+1,tmp+1+ct);
    ct=unique(tmp+1,tmp+1+ct)-tmp-1;
    rep(i,1,m){
        Insert(1,ct-1,1,lower_bound(tmp+1,tmp+1+ct,l[i])-tmp,lower_bound(tmp+1,tmp+1+ct,r[i]+1)-tmp-1,i);
    }
    dfs(1,ct-1,1);
    printf("%lld
",ans);
    return 0;
}
/*
7 8
1 2 1 4
1 3 2 6
2 4 2 5
2 5 3 3
3 6 5 5
4 7 3 4
5 7 2 3
6 7 5 5


*/