2454. Next Greater Element IV

You are given a 0-indexed array of non-negative integers nums. For each integer in nums, you must find its respective second greater integer.

The second greater integer of nums[i] is nums[j] such that:

• j > i
• nums[j] > nums[i]
• There exists exactly one index k such that nums[k] > nums[i] and i < k < j.

If there is no such nums[j], the second greater integer is considered to be -1.

• For example, in the array [1, 2, 4, 3], the second greater integer of 1 is 4, 2 is 3, and that of 3 and 4 is -1.

Return an integer array answer, where answer[i] is the second greater integer of nums[i].

c++

struct Seg {
    int mi, ma, v;
    Seg *left, *right;
    Seg (vector<int>& A, int l, int r) : mi(A[l]), ma(A[r]), v(INT_MAX), left(nullptr), right(nullptr) {
        if(l != r) {
            int m = l + (r - l) / 2;
            left = new Seg(A,l,m);
            right = new Seg(A,m+1,r);
        }
    }
    void update(int n, int p) {
        if(mi <= n and n <= ma) {
            v = min(v,p);
            if(left) left->update(n,p);
            if(right) right->update(n,p);
        }
    }

    int query(int n) {
        if(ma <= n) return INT_MAX;
        if(mi > n) return v;
        return min(left ? left->query(n) : 0, right ? right->query(n) : 0);
    }
};

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& A) {
        vector<int> S = A;
        sort(begin(S), end(S));
        S.erase(unique(begin(S), end(S)), end(S));
        Seg* seg = new Seg(S,0,S.size() - 1);
        vector<int> res(A.size(), -1);
        priority_queue<pair<int, int>> q;
        for(int i = A.size() - 1; i >= 0; i--) {
            int p = seg->query(A[i]);
            if(p < A.size()) q.push({p,i});
            seg->update(A[i],i);
        }
        int i = A.size() - 1;
        Seg* seg2 = new Seg(S,0,S.size() - 1);
        while(q.size()) {
            auto [pos, index] = q.top(); q.pop();
            while(i > pos) {
                seg2->update(A[i], i);
                i -= 1;
            }
            int p = seg2->query(A[index]);
            if(p < A.size()) res[index] = A[p];
        }
        return res;
    }
};