2519. Count the Number of K-Big Indices

You are given a 0-indexed integer array nums and a positive integer k.

We call an index i k-big if the following conditions are satisfied:

• There exist at least k different indices idx1 such that idx1 < i and nums[idx1] < nums[i].
• There exist at least k different indices idx2 such that idx2 > i and nums[idx2] < nums[i].

Return the number of k-big indices.

int fenwick[101010];

void update(int n) {
    while(n < 101010) {
        fenwick[n] += 1;
        n += n & -n;
    }
}

int query(int n) {
    int res = 0;
    while(n) {
        res += fenwick[n];
        n -= n & - n;
    }
    return res;
}

class Solution {
public:
    int kBigIndices(vector<int>& nums, int k) {
        vector<int> ok(nums.size(), true);
        memset(fenwick, 0, sizeof fenwick);
        for(int i = 0; i < nums.size(); i++) {
            int now = query(nums[i] - 1);
            if(now < k) ok[i] = false;
            update(nums[i]);
        }
        memset(fenwick, 0, sizeof fenwick);
        for(int i = nums.size() - 1; i >= 0; i--) {
            int now = query(nums[i] - 1);
            if(now < k) ok[i] = false;
            update(nums[i]);
        }
        return count(begin(ok), end(ok), true);
    }
};