3431. Minimum Unlocked Indices to Sort Nums

You are given an array nums consisting of integers between 1 and 3, and a binary array locked of the same size.

We consider nums sortable if it can be sorted using adjacent swaps, where a swap between two indices i and i + 1 is allowed if nums[i] - nums[i + 1] == 1 and locked[i] == 0.

In one operation, you can unlock any index i by setting locked[i] to 0.

Return the minimum number of operations needed to make nums sortable. If it is not possible to make nums sortable, return -1.

struct FW {
    vector<long long> fw;
    int siz;
    FW(int n) : siz(n + 1) {
        fw = vector<long long>(siz);
    }
    void update(int n, int x) {
        n += 1;
        while(n < siz) {
            fw[n] += x;
            n += n & -n;
        }
    }
    long long query(int n) {
        n += 1;
        long long res = 0;
        while(n > 0) {
            res += fw[n];
            n -= n & -n;
        }
        return res;
    }
};
class Solution {
public:
    int minUnlockedIndices(vector<int>& nums, vector<int>& locked) {
        int n = nums.size();
        FW lo(n + 1), on(n + 1);
        map<int,deque<int>> at;
        set<int> los;
        for(int i = 0; i < n; i++) {
            at[nums[i]].push_back(i);
            if(locked[i]) {
                lo.update(i,1);
                los.insert(i);
            }
        }
        vector<int> S = nums;
        sort(begin(S), end(S));
        int res = 0, processed = 0;
        auto cleanLock = [&]() {
            while(los.size() and *begin(los) < processed) {
                lo.update(*begin(los), -1);
                los.erase(*begin(los));
            }
        };
        while(at.size()) {
            deque<deque<int>> dq;
            int lookup = begin(at)->first;
            while(at.count(lookup)) {
                dq.push_back(at[lookup]);
                at.erase(lookup);
                lookup++;
            }
            while(dq.size() >= 2) {
                bool shouldSwap = false;
                while(dq[0].size()) {
                    int at = dq[0].front(); dq[0].pop_front();
                    on.update(at, 1);
                    processed++;
                    while(dq[1].size() and dq[1][0] < at) {
                        on.update(dq[1][0], 1);
                        processed++;
                        dq[1].pop_front();
                        shouldSwap = true;
                    }
                    if(on.query(at) != at + 1) return -1;
                    if(shouldSwap) {
                        res += lo.query(at - 1);

                    }
                    while(los.size() and *begin(los) <= at - shouldSwap) {
                        lo.update(*begin(los), -1);
                        los.erase(*begin(los));
                    }
                }
                dq.pop_front();
                cleanLock();
            }
            while(dq[0].size()) {
                int at = dq[0][0]; dq[0].pop_front();
                on.update(at, 1);
                processed++;
            }
            cleanLock();

            if(on.query(processed - 1) != processed) return -1;
        }
        return res;
    }
};

class Solution {
public:
    int minUnlockedIndices(vector<int>& nums, vector<int>& locked) {
        map<int,deque<int>> at;
        for(int i = 0; i < nums.size(); i++) at[nums[i]].push_back(i);
        int res = 0, sorted = -1;
        while(at.size()) {
            int val = begin(at)->first;
            int ops = 0, lookup = sorted + 1, carry = false;
            for(auto& p : begin(at)->second) {
                if(p == sorted + 1) {
                    if(carry) {
                        res += ops;
                        ops = locked[p];
                    } else ops = 0;
                    sorted = p, lookup = p + 1;
                } else {
                    for(; lookup < p; lookup++) {
                        if(nums[lookup] > val + 1) return -1;
                        ops += locked[lookup];
                        if(nums[lookup] == val + 1) at[val+1].pop_front();
                        carry = true;
                    }
                    res += ops; ops = locked[p];
                    sorted = p;
                    lookup = p + 1;
                }
            }
            at.erase(begin(at));
        }
        return res;
    }
};