2019 우 객 여름 다 교 훈련소 (제8 차 전) 익스플로러 (선분 수 분해 정 답)

original link - https://ac.nowcoder.com/acm/contest/888/E
제목:
n 개의 점, m 개의 변 을 제시 하고 각 변 에 범위 가 있 으 며 지정 한 범위 의 숫자 가 통과 할 수 있 습 니 다.지금 1, 1, 1 에 [1, 1 e 9] [1, 1 e9] [1, 1 e9] 가 있 습 니 다. n n 에 도착 하려 면 마지막 에 몇 개의 점 이 도착 할 수 있 는 지 물 어보 세 요.
해석:
직접 뒤 져 서 는 안 될 것 같 습 니 다. 우 리 는 분 치 를 고려 해 보 겠 습 니 다.
분할 구간 [L, R] [L, R] [L, R], 이 구간 을 포함 하 는 모든 변 을 연결 하여 1 → n 1 \ \ to n 1 → n 이 가능 한 지 확인 합 니 다.이것 은 수집 해서 조회 할 수 있다.
가능 하 다 면 [L, R] [L, R] [L, R] 을 설명 하고 답 을 계산 할 수 있 습 니 다.그렇지 않 으 면 우 리 는 [L, m i d], [m i d + 1, R] [L, mid], [mid + 1, R] [L, mid], [mid + 1, R] 을 판단 한다.
tip:
- 그리고 집합 은 거 슬러 올 라 갈 때 뜯 어야 하기 때문에 경로 가 압축 되 지 않 기 때문에 계발 식 합병 이 필요 합 니 다. -우 리 는 모든 변 을 대응 가능 한 집합 ([L, R] [L, R] [L, R] [L, R] [L, R] [L, R] [L, R] [L, R]] [L, R] [L, R] 을 포함 하고, 그 다음 에 [L, m i d] [L, mid] [L, mid] [L, mid]]] - 구간 을 이산 화 할 필요 가 없 기 때문에 구간 값 을 점 에 저장 해 야 한다. 이 체 조 는 R + 1, [g t (L), g e t (R + 1) - 1] R + 1, [get (L), [get (L) - 1) - 1, get (R + 1) - 1] R + 1, [get (L), [get (L), get (R + 1) - 1] - 1] - 1](g e t get 이산 화 i n d e x index index)
코드:

#include
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)

const int maxn=2e5+5;
int n,m;

struct Uni{
    int num;
    int a[maxn];
    void push(int p){
        a[++num]=p;
    }
    void init(){
        sort(a+1,a+1+num);
        num=unique(a+1,a+1+num)-a-1;
    }
    int pos(int val){
        return lower_bound(a+1,a+1+num,val)-a;
    }
}U;

struct edge{
    int l,r,u,v;
}e[maxn];

#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
vector<int>tr[maxn<<2];
void insert(int rt,int l,int r,int L,int R,int id){
    if(l>=L&&r<=R){
        tr[rt].push_back(id);
        return ;
    }
    if(L<=mid)
        insert(ls,l,mid,L,R,id);
    if(R>mid)
        insert(rs,mid+1,r,L,R,id);
}

#define pill pair
namespace link{
    int fa[maxn];
    int siz[maxn];
    void init(int n){
        rep(i,1,n)fa[i]=i,siz[i]=1;
    }
    int fin(int a){
        return fa[a]==a?a:fin(fa[a]);
    }
    stack<pill>sta;
    bool un(int a,int b){
        int f1=fin(a),f2=fin(b);
        if(f1==f2)return 0;
        if(siz[f1]>siz[f2])swap(f1,f2);
        fa[f1]=f2;
        sta.push({f1,f2});
        siz[f2]+=siz[f1];
        return 1;
    }
    void undo(int tim){
        while(tim--){
            auto p=sta.top();sta.pop();
            siz[p.second]-=siz[p.first];
            fa[p.first]=p.first;
        }
    }
}
using namespace link;

int ans;
void query(int rt,int l,int r){ //           
    int ct=0;
    for(auto i:tr[rt]){
        int u=e[i].u,v=e[i].v;
        un(u,v)&&++ct;
    }
    if(fin(1)==fin(n)){
        ans+=U.a[r+1]-U.a[l];
    }
    else if(l==r){
        ;
    }
    else{
        query(ls,l,mid);
        query(rs,mid+1,r);
    }
    undo(ct);
}

int main(){
    scanf("%d%d",&n,&m);
    U.num=0;
    rep(i,1,m){
        scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].r);
        U.push(e[i].l);
        U.push(e[i].r+1);
    }
    U.init();
    rep(i,1,m){
        e[i].l=U.pos(e[i].l);
        e[i].r=U.pos(e[i].r+1)-1;
        insert(1,1,U.num,e[i].l,e[i].r,i);
    }
    init(n);
    query(1,1,U.num);
    printf("%d
",ans);
}