链接：https://ac.nowcoder.com/acm/contest/888/E
来源：牛客网
Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.
There are nn_{}n vertices and mm_{}m bidirectional roads in this level, each road is in format (u,v,l,r)(u, v, l, r)_{}(u,v,l,r), which means that vertex uu_{}u and vv_{}v are connected by this road, but the sizes of passers should be in interval [l,r][l, r]_{}[l,r]. Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.
Moreover, vertex 11_{}1 is the starting point and vertex nn_{}n is the destination. Gromah and LZR should go from vertex 11_{}1 to vertex nn_{}n to enter the next level.
At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from 11_{}1 to nn_{}n.
Please help them to find the number of valid sizes.
输入描述:
The first line contains two positive integers n,mn,m_{}n,m, denoting the number of vertices and roads.
Following m lines each contains four positive integers u,v,l,ru, v, l, r_{}u,v,l,r, denoting a bidirectional road (u,v,l,r)(u, v, l, r)_{}(u,v,l,r).
1≤n,m≤105,1≤u<v≤n,1≤l≤r≤1091 \le n,m \le 10^5, 1 \le u < v \le n, 1 \le l \le r \le 10^91≤n,m≤105,1≤u<v≤n,1≤l≤r≤109
输出描述:
Print a non-negative integer in a single line, denoting the number of valid sizes.
示例1
输入
5 5
1 2 1 4
2 3 1 2
3 5 2 4
2 4 1 3
4 5 3 4
输出
2 题意：
给定ｍ条边，每条边有一个通过的阈值，问可以从１到n的值有多少个．
思路：
把这些边放入一个点表示区间的线段树里面．
这真是我从未见过的全新套路，在线段树上dfs，相当于枚举权值，由于每一个点代表区间，所以每次就枚举到了一个区间． 枚举之时用并查集判断．
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime> #define fuck(x) cerr<<#x<<" = "<<x<<endl;
#define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl;
#define lson l,mid,ls
#define rson mid+1,r,rs
#define ls (rt<<1)
#define rs ((rt<<1)|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int loveisblue = ;
const int maxn = ;
const int maxm = ;
const int inf = 0x3f3f3f3f;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int n,m;
struct edge{
int u,v,l,r;
}e[maxn];
int f[maxn],rk[maxn];
int rem[maxn],tot; vector<int>eg[maxn<<]; void update(int l,int r,int rt,int L,int R,int id){
if(rt==){ return;}
if(L<=l&&R>=r){
eg[rt].push_back(id);
return;
}
int mid = (l+r)>>;
if(L<=mid)update(l,mid,rt*,L,R,id);
if(R>mid)update(mid+,r,rt*+,L,R,id);
} int getf(int x){
if(x==f[x]){ return x;}
return getf(f[x]);
} int ans = ;
struct node{
int num,type;
}; void dfs(int l,int r,int rt){ stack<node>tmp;
for(auto it:eg[rt]){
int t1 = getf(e[it].u);
int t2 = getf(e[it].v);
if(rk[t1]<rk[t2]){
tmp.push(node{f[t1],});
f[t1]=f[t2];
}else if(rk[t1]>rk[t2]){
tmp.push(node{f[t2],});
f[t2]=f[t1];
}else{
tmp.push(node{f[t2],});
f[t2]=f[t1];
rk[t2]++;
}
} if(l==r){
if(getf()==getf(n)&&l!=tot){
ans+=rem[r+]-rem[l];
}
while (!tmp.empty()){
node it = tmp.top();
tmp.pop();
f[it.num]=it.num;
if(it.type==){
rk[it.num]--;
}
}
return;
}
int mid = (l+r)>>;
dfs(lson);
dfs(rson);
while (!tmp.empty()){
node it = tmp.top();
tmp.pop();
f[it.num]=it.num;
if(it.type==){
rk[it.num]--;
}
}
} int get_id(int x){
return lower_bound(rem+,rem++tot,x)-rem;
} int main() { scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
f[i]=i;
rk[i]=;
} for(int i=;i<=m;i++){
scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].l,&e[i].r);
rem[++tot] = e[i].l;
rem[++tot] = e[i].r+;
}
sort(rem+,rem++tot);
tot = unique(rem+,rem++tot)-rem-; for(int i=;i<=m;i++){
cout<<get_id(e[i].l)<<" "<<get_id(e[i].r+)-<<endl;
update(,tot,,get_id(e[i].l),get_id(e[i].r+)-,i);
}
dfs(,tot,);
printf("%d\n",ans);
return ;
}
