记录编号	581081	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.458 s
提交时间	2023-07-28 17:27:22	内存使用	5.65 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n,m,ans;
int pre[N];
int fa(int x){
    if(x == pre[x])return x;
    return pre[x] = fa(pre[x]);
}//查找并查集祖先节点，并进行路径压缩 
int main(){
    freopen("axis.in","r",stdin);
    freopen("axis.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)pre[i] = i;//自己将自己连一起，0连0 
    //给一段区间染色,可以看做是合并一段区间,并且使其在统计过程中不会重复统计
    for(int i = 1;i <= m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        y = fa(y);
        while(x <= y){//直到查完 
            if(x != y && fa(x) == fa(y))break;
            pre[y] = fa(pre[y-1]);//将y的父亲连为y-1，并路径压缩 
            ans++;
            y = pre[y];
        }
        printf("%d\n",n-ans);
    }
    
    return 0;
    
}