2019 ICPC 徐州网络赛 B.so easy (并查集)

题目链接：https://nanti.jisuanke.com/t/41384

题目大意

给定n个数，从1到n排列，其中有q次操作，操作(1) 删除一个数字 // 操作(2)求这个数字之后第一个没有被删除的数字（包括自己）。

思路

本题就是考的并查集的路径压缩，让每一次find，可以达到O(1)级别，每次删除x的时候，把fa[x] = x+1即可，这样x+1如果也是被删除的，那么fa[x+1] = x+1，这样循环下去肯定会到达x后第一个没有被删除的，这个过程经过路径压缩之后，每一次询问就是O(1)了。

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N,Q;
unordered_map<int,int> fa;

inline void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}

int find(int x){
    return fa.count(x)==0? x: fa[x] = find(fa[x]);
}
void join(int x,int y){
    fa[x] = y;
}
int main(){
    read(N),read(Q);
    while(Q--){
        int op,x;read(op),read(x);
        if(op == 1){
            join(x,x+1);
        }else{
            printf("%d\n",find(x));
        }
    }
    return 0;
}