2832. Maximal Range That Each Element Is Maximum in It

You are given a 0-indexed array nums of distinct integers.

Let us define a 0-indexed array ans of the same length as nums in the following way:

• ans[i] is the maximum length of a subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i].

Return the array ans.

Note that a subarray is a contiguous part of the array.

int uf[101010], sz[101010];
int find(int u) {
    return uf[u] == u? u : uf[u] = find(uf[u]);
}
int uni(int u, int v) {
    int pu = find(u), pv = find(v);
    sz[pu] = sz[pv] = sz[pu] + sz[pv];
    uf[pu] = uf[pv] = min(pu,pv);
    return sz[pu];
}
class Solution {
public:
    vector<int> maximumLengthOfRanges(vector<int>& nums) {
        int n = nums.size();
        vector<int> ord(n), on(n), res(n);
        for(int i = 0; i < n; i++) ord[i] = uf[i] = i, sz[i] = 1;
        sort(begin(ord), end(ord), [&](int i, int j) {return nums[i]<nums[j];});
        for(int i = 0; i < n; i++) {
            int p = ord[i], ma = 1;
            on[p] = true;
            if(p - 1 >= 0 and on[p-1]) {
                ma = max(ma, uni(p,p-1));
            }
            if(p + 1 < n and on[p+1]) {
                ma = max(ma, uni(p,p+1));
            }
            res[p] = ma;
        }
        return res;
    }
};