dsu题集

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

const int N = 1e5+5;
struct Node{ int a,b; bool operator < ( const Node &tmp)const{ return b<tmp.b; } }node[N];

int n,cnt,mxcnt,ans;
int arr[N],fa[N],num[N],sum[N];

int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }

inline void Union(int x,int y){
    x=find(x),y=find(y);
    sum[num[x]]--,sum[num[y]]--;      //表示对应集合数量的统计--
    num[x]+=num[y];sum[num[x]]++;     //y集合合并到x集合上
    fa[y]=x;cnt--;            //cnt表示当前集合的数量
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        node[i].b=arr[i];node[i].a=i;
        fa[i]=i;
    }
    sort(node+1,node+n+1);        
    for(int i=1;i<=n;i++){     //按序列中元素的大小从小到大考虑,枚举第i个元素，表示将k设为node[i].b+1
        int loc=node[i].a,val=node[i].b;
        num[loc]++;sum[num[loc]]++;   //初始化当前元素所在集合      
        cnt++;
        if(loc!=n&&val>arr[loc+1])Union(loc,loc+1); //因为当前k是设为node[i].b+1,所以该元素与原序列两边的元素比较，如果大于该元素，则说明他们在同一集合
        if(loc!=1&&val>arr[loc-1])Union(loc,loc-1);
        if(cnt==sum[num[find(loc)]]){       //判断是否所有集合的元素数量相同(判断是否满足题目条件)
            if(cnt>mxcnt)mxcnt=cnt,ans=val+1;
        }
    }
    printf("%d\n",ans);
}