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

这里线段树不能离散化，n<1e9。但是我们发现询问只有1e6。最多修改1e6次。
如果用动态开点。每次最多修改logn个点。空间复杂度O(1e6*log(1e6))。

或者用并查集

#include<bits/stdc++.h>
#define mid (l+r)/2
using namespace std;

int L[15000005]={0}, R[15000005]={0}, sum[15000005]={0}, add[15000005]={0};
int tot=1, n;

int build(int l, int r, int i)//开点
{
    ++tot;
    L[tot]=R[tot]=0;

    sum[tot]=n+1;

    return tot;

}

int update(int p, int l, int r, int i, int v)//更新
{
    if(l==r)//找到点
    {
        sum[p]=n+1;
        return 0;
    }
    if(i<=mid)
    {
        if(!L[p])
        {
            L[p]=build(l, mid, i);
        }

        update(L[p], l, mid, i, v);

    }
    else
    {
        if(!R[p])
        {
            R[p]=build(mid+1, r, i);
        }

        update(R[p], mid+1, r, i, v);

    }
    if(L[p]==0){
        sum[p]=l;
    }
    else if(R[p]==0)
    {
        sum[p]=min(sum[L[p]], mid+1);//递归求和
    }
    else
    sum[p]=min(sum[L[p]], sum[R[p]]);//递归求和
}

int ans=n+1;
int cx(int p, int l, int r, int LL, int RR)
{
    if(LL>RR){
        ans=min(ans, n+1);
        return 0;
    }
    if(l==LL&&r==RR)//区间查询
    {
        ans=min(ans, sum[p]);
        return 0;
    }
    if(RR<=mid)
    {
        if(L[p]==0){
            ans=min(ans, LL);
            return 0;
        }
        cx(L[p], l, mid, LL, RR);
    }
    else if(LL>=mid+1)
    {
        if(R[p]==0){
            ans=min(ans, LL);
            return 0;
        }
        cx(R[p], mid+1, r, LL, RR);
    }
    else
    {
        if(L[p]==0){
            ans=min(ans, LL);
        }
        else
        cx(L[p], l, mid, LL, mid);

        if(R[p]==0){
            ans=min(ans, mid+1);
        }
        else
        ans=min(ans, sum[R[p]]);
    }
}


inline int read(){
   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();
   return s*w;
}

int main()
{
    int m;
    scanf("%d%d",&n, &m);
    tot=1;
    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));
    while(m--){
        ans=n+1;
        int x, y;
        x=read(), y=read();
        if(x==1){
            update(1, 1, n, y, 1);
        }
        else{
            cx(1, 1, n, y, n);
            printf("%d\n", (ans==n+1)?-1:ans);
        }
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> mp;

int Find(int x){
    if(!mp.count(x)){
        return x;
    }
    return mp[x]=Find(mp[x]);
}

int main()
{
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    while(m--){
        scanf("%d%d", &x, &y);
        if(x==1){
            mp[y]=Find(y+1);
        }
        else{
            int ans=Find(y);
            if(ans>n){
                ans=-1;
            }
            printf("%d\n", ans);
        }
    }

    return 0;
}