D. Harmonious Graph

time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

You’re given an undirected graph with n nodes and m edges. Nodes are numbered from 1 to n.

The graph is considered harmonious if and only if the following property holds:

For every triple of integers (l,m,r) such that 1≤l<m<r≤n, if there exists a path going from node l to node r, then there exists a path going from node l to node m.
In other words, in a harmonious graph, if from a node l we can reach a node r through edges (l<r), then we should able to reach nodes (l+1),(l+2),…,(r−1) too.

What is the minimum number of edges we need to add to make the graph harmonious?

Input
The first line contains two integers n and m (3≤n≤200 000 and 1≤m≤200 000).

The i-th of the next m lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), that mean that there’s an edge between nodes u and v.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).

Output
Print the minimum number of edges we have to add to the graph to make it harmonious.

Examples
inputCopy
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
outputCopy
1

inputCopy
200000 3
7 9
9 8
4 5
outputCopy
0

Note
In the first example, the given graph is not harmonious (for instance, 1<6<7, node 1 can reach node 7 through the path 1→2→7, but node 1 can’t reach node 6). However adding the edge (2,4) is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

比较显然的是，如果对于当前的联通块当中，有一个编号比当前联通块的最小编号大，比最大编号小，那么肯定需要与这个联通块链接起来。

所以我们维护连通性即可，用并查集最好。

但是每次从最小到最大编号枚举肯定会TLE，所以我们枚举点即可，因为一个点只会被枚举一次，所以我们通过维护下限，来剪枝。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,res,f[N],j=1;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void merge(int x,int y){
	x=find(x);	y=find(y);	f[min(x,y)]=max(x,y);
}
signed main(){
	cin>>n>>m;	for(int i=1;i<=n;i++)	f[i]=i;
	for(int i=1,a,b;i<=m;i++)	scanf("%d %d",&a,&b),merge(a,b);
	for(int i=1;i<n;i++){
		int r=find(i);
		for(;j<=r;j++){
			if(find(j)!=find(i))	merge(j,r),res++;
		}	j=r+1;
	}
	cout<<res<<endl;
	return 0;
}