4013. Count Subarrays With Even Odd Ratio II

Description

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

For a subarray, let:

x be the number of even elements.
y be the number of odd elements.

The ratio of even to odd elements in a subarray is defined as x / y, where ratios are compared by their exact rational values.

A subarray is considered valid if:

y > 0, and
x / y <= a / b.

Return the number of valid subarrays in nums.

Example 1:

Input: nums = [1,2,1,2], a = 3, b = 2

Output: 7

Explanation:

The following are the valid subarrays:

Subarray	Values	Even Count	Odd Count	Ratio
`nums[0..0]`	`[1]`	0	1	`0 / 1`
`nums[0..1]`	`[1, 2]`	1	1	`1 / 1`
`nums[0..2]`	`[1, 2, 1]`	1	2	`1 / 2`
`nums[0..3]`	`[1, 2, 1, 2]`	2	2	`2 / 2`
`nums[1..2]`	`[2, 1]`	1	1	`1 / 1`
`nums[2..2]`	`[1]`	0	1	`0 / 1`
`nums[2..3]`	`[1, 2]`	1	1	`1 / 1`

Thus, the number of valid subarrays is 7.

Example 2:

Input: nums = [2,2,1], a = 2, b = 1

Output: 3

Explanation:

The following are the valid subarrays:

Subarray	Values	Even Count	Odd Count	Ratio
`nums[0..2]`	`[2, 2, 1]`	2	1	`2 / 1`
`nums[1..2]`	`[2, 1]`	1	1	`1 / 1`
`nums[2..2]`	`[1]`	0	1	`0 / 1`

Thus, the number of valid subarrays is 3.

Example 3:

Input: nums = [2,2,2], a = 1, b = 1

Output: 0

Explanation:

Every subarray contains 0 odd numbers, so no subarray is valid.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= a, b <= 10⁹

Solutions

Solution 1: Prefix Sum + Binary Indexed Tree

Thinking

The quadratic enumeration of the previous problem does not survive \(n=10^5\). The condition \(y>0\) and \(\frac{x}{y}\le\frac{a}{b}\) rewrites as \(ay-bx\ge 0\) when \(b>0\); an all-even subarray makes the same expression negative, so both constraints merge.

Mapping odds to \(+a\) and evens to \(-b\), we count nonempty subarrays whose sum is at least \(0\), i.e. prefix pairs with \(s[L]\le s[R]\).

Scanning \(R\), a Fenwick tree on the compressed prefix values stores how many earlier \(s[L]\) have appeared, we query those \(\le s[R]\), then insert the current value.

For a subarray, let \(x\) be the number of even elements and \(y\) be the number of odd elements. The problem requires \(y > 0\) and \(\frac{x}{y} \le \frac{a}{b}\). Since \(b > 0\) and \(y > 0\), the inequality is equivalent to \(a \cdot y - b \cdot x \ge 0\).

When \(y = 0\), since the subarray is non-empty, we must have \(x > 0\). In this case, \(a \cdot y - b \cdot x = -b \cdot x < 0\), so the inequality does not hold. Therefore, the two conditions in the problem can be merged into a single one: \(a \cdot y - b \cdot x \ge 0\).

We treat the odd numbers in \(\textit{nums}\) as \(a\) and the even numbers as \(-b\), resulting in an array \(\textit{arr}\). The original problem is then equivalent to counting the number of non-empty contiguous subarrays of \(\textit{arr}\) whose element sum is at least \(0\).

Let \(s\) be the prefix sum array of \(\textit{arr}\). The element sum of the subarray \([L, R - 1]\) equals \(s[R] - s[L]\), so the problem is further transformed into: how many index pairs \((L, R)\) satisfy \(0 \le L < R \le n\) and \(s[R] - s[L] \ge 0\), i.e., \(s[L] \le s[R]\)?

We enumerate \(R\) and need to quickly count the number of indices \(L\) to the left of \(R\) that satisfy \(s[L] \le s[R]\). This can be maintained with a Binary Indexed Tree: we first discretize all values in \(s\) (sort and deduplicate), then traverse \(s\) from left to right. For each value \(v = s[R]\), we query the number of inserted elements not greater than \(v\) from the Binary Indexed Tree and add it to the answer, then insert \(v\) into the tree.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScriptRust

class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def countRatioSubarrays(self, nums: list[int], a: int, b: int) -> int:
        n = len(nums)
        s = [0] * (n + 1)
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + (a if x % 2 else -b)

        st = sorted(set(s))
        bit = BinaryIndexedTree(len(st) + 1)
        ans = 0
        for v in s:
            x = bisect_left(st, v) + 1
            ans += bit.query(x)
            bit.update(x, 1)
        return ans

class BinaryIndexedTree {
    private final int n;
    private final int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    public void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
}

class Solution {
    public long countRatioSubarrays(int[] nums, int a, int b) {
        int n = nums.length;

        long[] s = new long[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + (nums[i] % 2 == 1 ? a : -b);
        }

        long[] st = s.clone();
        Arrays.sort(st);

        int m = 0;
        for (long x : st) {
            if (m == 0 || st[m - 1] != x) {
                st[m++] = x;
            }
        }

        BinaryIndexedTree bit = new BinaryIndexedTree(m + 1);

        long ans = 0;

        for (long v : s) {
            int x = Arrays.binarySearch(st, 0, m, v) + 1;
            ans += bit.query(x);
            bit.update(x, 1);
        }

        return ans;
    }
}

class BinaryIndexedTree {
    int n;
    vector<int> c;

public:
    BinaryIndexedTree(int n)
        : n(n)
        , c(n + 1) {}

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
};

class Solution {
public:
    long long countRatioSubarrays(vector<int>& nums, int a, int b) {
        int n = nums.size();

        vector<long long> s(n + 1);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + (nums[i] % 2 ? a : -b);
        }

        vector<long long> st = s;
        sort(st.begin(), st.end());
        st.erase(unique(st.begin(), st.end()), st.end());

        BinaryIndexedTree bit(st.size() + 1);

        long long ans = 0;

        for (long long v : s) {
            int x = lower_bound(st.begin(), st.end(), v) - st.begin() + 1;
            ans += bit.query(x);
            bit.update(x, 1);
        }

        return ans;
    }
};

type BinaryIndexedTree struct {
    n int
    c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
    return &BinaryIndexedTree{
        n: n,
        c: make([]int, n+1),
    }
}

func (bit *BinaryIndexedTree) update(x int, delta int) {
    for x <= bit.n {
        bit.c[x] += delta
        x += x & -x
    }
}

func (bit *BinaryIndexedTree) query(x int) int {
    sum := 0
    for x > 0 {
        sum += bit.c[x]
        x -= x & -x
    }
    return sum
}

func countRatioSubarrays(nums []int, a int, b int) int64 {
    n := len(nums)

    s := make([]int64, n+1)

    for i, x := range nums {
        if x%2 == 1 {
            s[i+1] = s[i] + int64(a)
        } else {
            s[i+1] = s[i] - int64(b)
        }
    }

    st := append([]int64{}, s...)
    sort.Slice(st, func(i, j int) bool {
        return st[i] < st[j]
    })

    uniq := make([]int64, 0, len(st))
    for _, x := range st {
        if len(uniq) == 0 || uniq[len(uniq)-1] != x {
            uniq = append(uniq, x)
        }
    }

    bit := NewBinaryIndexedTree(len(uniq) + 1)

    var ans int64

    for _, v := range s {
        x := sort.Search(len(uniq), func(i int) bool {
            return uniq[i] >= v
        }) + 1

        ans += int64(bit.query(x))
        bit.update(x, 1)
    }

    return ans
}

class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = new Array(n + 1).fill(0);
    }

    update(x: number, delta: number): void {
        while (x <= this.n) {
            this.c[x] += delta;
            x += x & -x;
        }
    }

    query(x: number): number {
        let sum = 0;
        while (x > 0) {
            sum += this.c[x];
            x -= x & -x;
        }
        return sum;
    }
}

function countRatioSubarrays(nums: number[], a: number, b: number): number {
    const n = nums.length;

    const s = new Array<number>(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + (nums[i] % 2 === 1 ? a : -b);
    }

    const st = [...s].sort((x, y) => x - y);

    const uniq: number[] = [];
    for (const x of st) {
        if (uniq.length === 0 || uniq[uniq.length - 1] !== x) {
            uniq.push(x);
        }
    }

    const bit = new BinaryIndexedTree(uniq.length + 1);

    let ans = 0;

    for (const v of s) {
        const x = _.sortedIndex(uniq, v) + 1;

        ans += bit.query(x);
        bit.update(x, 1);
    }

    return ans;
}

struct BinaryIndexedTree {
    n: usize,
    c: Vec<i32>,
}

impl BinaryIndexedTree {
    fn new(n: usize) -> Self {
        Self {
            n,
            c: vec![0; n + 1],
        }
    }

    fn update(&mut self, mut x: usize, delta: i32) {
        while x <= self.n {
            self.c[x] += delta;
            x += x & (!x + 1);
        }
    }

    fn query(&self, mut x: usize) -> i32 {
        let mut s = 0;
        while x > 0 {
            s += self.c[x];
            x &= x - 1;
        }
        s
    }
}

impl Solution {
    pub fn count_ratio_subarrays(nums: Vec<i32>, a: i32, b: i32) -> i64 {
        let n = nums.len();

        let mut s = vec![0i64; n + 1];

        for i in 0..n {
            s[i + 1] = s[i]
                + if nums[i] % 2 == 1 {
                    a as i64
                } else {
                    -(b as i64)
                };
        }

        let mut st = s.clone();
        st.sort_unstable();
        st.dedup();

        let mut bit = BinaryIndexedTree::new(st.len() + 1);

        let mut ans = 0i64;

        for v in s {
            let x = match st.binary_search(&v) {
                Ok(i) => i,
                Err(i) => i,
            } + 1;

            ans += bit.query(x) as i64;
            bit.update(x, 1);
        }

        ans
    }
}

4013. Count Subarrays With Even Odd Ratio II

Description

Solutions

Solution 1: Prefix Sum + Binary Indexed Tree

Comments