【題解】LeetCode 1562. Find Latest Group of Size M

class Solution {
public:
    int p[100005] = {};
    int pa(int x){
        if (p[x] < 0) return x;
        if (p[x] == 0) return x;
        return p[x] = pa(p[x]);
    }
    int findLatestStep(vector<int>& arr, int m) {
        int cnt = 0, ans = 0;
        for (int i = 0; i < arr.size(); i++){
            int l = pa(arr[i]-1), r = pa(arr[i]+1);
            if (p[l] == -m) cnt--;
            if (p[r] == -m) cnt--;
            p[arr[i]] = -1;
            if (p[l]){
                p[arr[i]] += p[l];
                p[l] = arr[i];
            }
            if (p[r]){
                p[arr[i]] += p[r];
                p[r] = arr[i];
            }
            if (-p[arr[i]] == m) cnt++;
            if (cnt) ans = max(ans, i+1);
        }
        if (ans == 0) return -1;
        return ans;
    }
};