并查集维护序列信息

1562. 查找大小为M的最新分组

参考自大佬的视频教程：https://www.bilibili.com/video/BV1Xp4y1v7Nj?p=4

• 用并查集维护1的连通信息
• 具体来说：f[i]表示i所在的连续1的代表节点的位置，这里我们选用的代表节点是连续一段1右侧第一个0的位置。思考题：为什么选这个位置呢？能否选其他位置呢？
• 并查集维护额外信息：siz[i]维护的是某一段连续1的长度，该段代表节点为i。
• cnt[i]维护siz[i]==i的数量，类似于桶排序，cnt[i]=3表示有3段连续1的长度为i。

code

const int M=1e5+5;
int f[M],siz[M],cnt[M];
class Solution {
public:
    int find(int x)
    {
        if (x!=f[x])
            f[x]=find(f[x]);
        return f[x];
    }
    int findLatestStep(vector<int>& arr, int m) 
    {
        int n=arr.size();
        for (int i=0;i<=n+1;i++)
        {
            f[i]=i;
            siz[i]=0;
            cnt[i]=0;
        }
        cnt[0]=n;
        int ans=-1;
        for (int i=0;i<n;i++)
        {
            int p=arr[i];
            f[p]=p+1;
            int fp=find(p);
            cnt[siz[p]]--;
            cnt[siz[fp]]--;
            siz[fp]=siz[p]+siz[fp]+1;
            siz[p]=0;
            cnt[siz[fp]]++;
            if (cnt[m])
                ans=i+1;
        }
        return ans;
    }
};