3994. Minimum Adjacent Swaps to Partition Array

You are given an integer array nums and two integers a and b such that a < b.

An array is called good if it can be split into three contiguous parts, in this order, such that:

• Every element in the first part is less than a.
• Every element in the second part is in the range [a, b] inclusive.
• Every element in the third part is greater than b.

Any of the three parts may be empty.

In one adjacent swap, you may swap two neighboring elements of nums.

Return the minimum number of adjacent swaps required to make nums good. Since the answer may be very large, return it modulo 10^9 + 7.

class Solution {
public:
    int minAdjacentSwaps(vector<int>& nums, int a, int b) {
        int less = 0, res = 0, mid = 0, over = 0, mod = 1e9 + 7;
        for(auto& n : nums) {
            if(n < a) less++;
            else if(n > b) over++;
            else mid++;
        }
        auto work = [&](int limit, vector<int>& A) {
            int res = 0;
            for(int i = 0, cnt = 0; i < A.size(); i++) {
                if(A[i] >= limit) continue;
                res = (res + i - cnt) % mod;
                cnt++;
            }
            return res;
        };
        res = work(a,nums);
        vector<int> A;
        for(auto& n : nums) if(n >= a) A.push_back(n);
        res = (res + work(b+1,A)) % mod;
        return res;
    }
};