3739. Count Subarrays With Majority Element II

You are given an integer array nums and an integer target.

Return the number of subarrays of nums in which target is the majority element.

The majority element of a subarray is the element that appears strictly more than half of the times in that subarray.

struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick(int n=0): n(n), bit(n+1,0) {}
    void add(int i, long long v=1){ for(; i<=n; i += i&-i) bit[i]+=v; }
    long long sum(int i){ long long r=0; for(; i>0; i -= i&-i) r += bit[i]; return r; }
};

class Solution {
public:
    long long countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        vector<long long> pre(n+1);
        for(int i=0;i<n;i++) pre[i+1] = pre[i] + ((nums[i]==target) ? 1 : -1);

        vector<long long > A = pre;
        sort(begin(A), end(A));
        A.erase(unique(begin(A), end(A)), end(A));
        auto at = [&](long long x) {
            return lower_bound(begin(A), end(A), x) - begin(A) + 1;
        };

        Fenwick fw(A.size());
        long long res = 0;
        for(int i=0;i<=n;i++){
            int x = at(pre[i]);
            if(x - 1 >= 1) res += fw.sum(x - 1);
            fw.add(x, 1);
        }
        return res;
    }
};