2019牛客暑期多校训练营（第八场）E Explorer
题目链接： https://ac.nowcoder.com/acm/contest/888/E
题意：
有一张n个点m条边的图，每条边上会有一个可通过数字的边界限制
[
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这条边。注意这里的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]去做。做完之后要将并查集进行拆分，就是令被合并的那些值的fa变回他们自己,(我在合并的时候就是找过父亲的根了的，所以拆分的时候变成自己是合理的)。
这里还有一个问题，就是在并查集的时候，是不可以用路径压缩优化的，因为你在拆分的时候，只将根变回了它自己，在fin的过程当中，可能会将非根的值进行变化，这样就会无法变回去，从而使得答案错误。但是如果路径不压缩，直接做就会T，所以需要用到一个叫做启发式合并的东西，需要用到sz数组，记录每个集合的当前大小，这样就可以使得路径数变短啦。
如果不清楚为什么是
t
m
p
[
r
+
1
]
−
t
m
p
[
l
]
tmp[r+1]-tmp[l]
tmp[r+1]−tmp[l]，可以戳上面小窗口的链接，下面的
c
n
t
−
1
cnt-1
cnt−1是为了抛弃掉最后一个数字，至于为什么要抛弃，因为它一定是某一个被++了的右区间，没有意义所以不需要被囊括进合法区间内。
代码：
#include<bits/stdc++.h>
#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\n",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
*/