Skip to content

3748. Count Stable Subarrays

Description

You are given an integer array nums.

A subarray of nums is called stable if it contains no inversions, i.e., there is no pair of indices i < j such that nums[i] > nums[j].

You are also given a 2D integer array queries of length q, where each queries[i] = [li, ri] represents a query. For each query [li, ri], compute the number of stable subarrays that lie entirely within the segment nums[li..ri].

Return an integer array ans of length q, where ans[i] is the answer to the ith query.​​​​​​​​​​​​​​

Note:

  • A single element subarray is considered stable.

 

Example 1:

Input: nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]

Output: [2,3,4]

Explanation:​​​​​

  • For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].
    • The stable subarrays are [3] and [1]. The total number of stable subarrays is 2.
  • For queries[1] = [1, 2], the subarray is [nums[1], nums[2]] = [1, 2].
    • The stable subarrays are [1], [2], and [1, 2]. The total number of stable subarrays is 3.
  • For queries[2] = [0, 2], the subarray is [nums[0], nums[1], nums[2]] = [3, 1, 2].
    • The stable subarrays are [3], [1], [2], and [1, 2]. The total number of stable subarrays is 4.

Thus, ans = [2, 3, 4].

Example 2:

Input: nums = [2,2], queries = [[0,1],[0,0]]

Output: [3,1]

Explanation:

  • For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].
    • The stable subarrays are [2], [2], and [2, 2]. The total number of stable subarrays is 3.
  • For queries[1] = [0, 0], the subarray is [nums[0]] = [2].
    • The stable subarray is [2]. The total number of stable subarrays is 1.

Thus, ans = [3, 1].

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i] = [li, ri]
  • 0 <= li <= ri <= nums.length - 1

Solutions

Solution 1: Segmented Counting

According to the problem description, a stable subarray is defined as a subarray without inversion pairs, meaning the elements in the subarray are arranged in non-decreasing order. Therefore, we can divide the array into several non-decreasing segments, using an array \(\text{seg}\) to record the starting position of each segment. At the same time, we need a prefix sum array \(\text{s}\) to record the number of stable subarrays within each segment.

Then, for each query \([l, r]\), there may be 3 cases:

  1. The query interval \([l, r]\) is completely contained within a single segment. In this case, the number of stable subarrays can be directly calculated using the formula \(\frac{(k + 1) \cdot k}{2}\), where \(k = r - l + 1\).
  2. The query interval \([l, r]\) spans multiple segments. In this case, we need to separately calculate the number of stable subarrays in the left incomplete segment, the right incomplete segment, and the complete segments in the middle, then add them together to get the final result.

The time complexity is \(O((n + q) \log n)\), where \(n\) is the length of the array and \(q\) is the number of queries. The space complexity is \(O(n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def countStableSubarrays(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        s = [0]
        l, n = 0, len(nums)
        seg = []
        for r, x in enumerate(nums):
            if r == n - 1 or x > nums[r + 1]:
                seg.append(l)
                k = r - l + 1
                s.append(s[-1] + (1 + k) * k // 2)
                l = r + 1
        ans = []
        for l, r in queries:
            i = bisect_right(seg, l)
            j = bisect_right(seg, r) - 1
            if i > j:
                k = r - l + 1
                ans.append((1 + k) * k // 2)
            else:
                a = seg[i] - l
                b = r - seg[j] + 1
                ans.append((1 + a) * a // 2 + s[j] - s[i] + (1 + b) * b // 2)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public long[] countStableSubarrays(int[] nums, int[][] queries) {
        List<Integer> seg = new ArrayList<>();
        List<Long> s = new ArrayList<>();
        s.add(0L);

        int l = 0;
        int n = nums.length;
        for (int r = 0; r < n; r++) {
            if (r == n - 1 || nums[r] > nums[r + 1]) {
                seg.add(l);
                int k = r - l + 1;
                s.add(s.getLast() + (long) k * (k + 1) / 2);
                l = r + 1;
            }
        }

        long[] ans = new long[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int left = queries[q][0];
            int right = queries[q][1];

            int i = upperBound(seg, left);
            int j = upperBound(seg, right) - 1;

            if (i > j) {
                int k = right - left + 1;
                ans[q] = (long) k * (k + 1) / 2;
            } else {
                int a = seg.get(i) - left;
                int b = right - seg.get(j) + 1;
                ans[q] = (long) a * (a + 1) / 2 + s.get(j) - s.get(i) + (long) b * (b + 1) / 2;
            }
        }
        return ans;
    }

    private int upperBound(List<Integer> list, int target) {
        int l = 0, r = list.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (list.get(mid) > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> seg;
        vector<long long> s = {0};

        int l = 0;
        for (int r = 0; r < n; ++r) {
            if (r == n - 1 || nums[r] > nums[r + 1]) {
                seg.push_back(l);
                long long k = r - l + 1;
                s.push_back(s.back() + k * (k + 1) / 2);
                l = r + 1;
            }
        }

        vector<long long> ans;
        for (auto& q : queries) {
            int left = q[0], right = q[1];

            int i = upper_bound(seg.begin(), seg.end(), left) - seg.begin();
            int j = upper_bound(seg.begin(), seg.end(), right) - seg.begin() - 1;

            if (i > j) {
                long long k = right - left + 1;
                ans.push_back(k * (k + 1) / 2);
            } else {
                long long a = seg[i] - left;
                long long b = right - seg[j] + 1;
                ans.push_back(a * (a + 1) / 2 + s[j] - s[i] + b * (b + 1) / 2);
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func countStableSubarrays(nums []int, queries [][]int) []int64 {
    n := len(nums)
    seg := []int{}
    s := []int64{0}

    l := 0
    for r := 0; r < n; r++ {
        if r == n-1 || nums[r] > nums[r+1] {
            seg = append(seg, l)
            k := int64(r - l + 1)
            s = append(s, s[len(s)-1]+k*(k+1)/2)
            l = r + 1
        }
    }

    ans := make([]int64, len(queries))
    for idx, q := range queries {
        left, right := q[0], q[1]

        i := sort.SearchInts(seg, left+1)
        j := sort.SearchInts(seg, right+1) - 1

        if i > j {
            k := int64(right - left + 1)
            ans[idx] = k * (k + 1) / 2
        } else {
            a := int64(seg[i] - left)
            b := int64(right - seg[j] + 1)
            ans[idx] = a*(a+1)/2 + s[j] - s[i] + b*(b+1)/2
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function countStableSubarrays(nums: number[], queries: number[][]): number[] {
    const n = nums.length;
    const seg: number[] = [];
    const s: number[] = [0];

    let l = 0;
    for (let r = 0; r < n; r++) {
        if (r === n - 1 || nums[r] > nums[r + 1]) {
            seg.push(l);
            const k = r - l + 1;
            s.push(s[s.length - 1] + (k * (k + 1)) / 2);
            l = r + 1;
        }
    }

    const ans: number[] = [];
    for (const [left, right] of queries) {
        const i = _.sortedIndex(seg, left + 1);
        const j = _.sortedIndex(seg, right + 1) - 1;

        if (i > j) {
            const k = right - left + 1;
            ans.push((k * (k + 1)) / 2);
        } else {
            const a = seg[i] - left;
            const b = right - seg[j] + 1;
            ans.push((a * (a + 1)) / 2 + s[j] - s[i] + (b * (b + 1)) / 2);
        }
    }

    return ans;
}

Comments