3748. Count Stable Subarrays Hard

1/**
2 * [3748] Count Stable Subarrays
3 *
4 * You are given an integer array nums.
5 * A <span data-keyword="subarray-nonempty">subarray</span> 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].
6 * 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].
7 * Return an integer array ans of length q, where ans[i] is the answer to the i^th query.​​​​​​​​​​​​​​
8 * Note:
9 * 
10 * 	A single element subarray is considered stable.
11 * 
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]</span>
16 * Output: <span class="example-io">[2,3,4]</span>
17 * Explanation:​​​​​
18 * 
19 * 	For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].
20 * 	
21 * 		The stable subarrays are [3] and [1]. The total number of stable subarrays is 2.
22 * 	
23 * 	
24 * 	For queries[1] = [1, 2], the subarray is [nums[1], nums[2]] = [1, 2].
25 * 	
26 * 		The stable subarrays are [1], [2], and [1, 2]. The total number of stable subarrays is 3.
27 * 	
28 * 	
29 * 	For queries[2] = [0, 2], the subarray is [nums[0], nums[1], nums[2]] = [3, 1, 2].
30 * 	
31 * 		The stable subarrays are [3], [1], [2], and [1, 2]. The total number of stable subarrays is 4.
32 * 	
33 * 	
34 * 
35 * Thus, ans = [2, 3, 4].
36 * </div>
37 * <strong class="example">Example 2:
38 * <div class="example-block">
39 * Input: <span class="example-io">nums = [2,2], queries = [[0,1],[0,0]]</span>
40 * Output: <span class="example-io">[3,1]</span>
41 * Explanation:
42 * 
43 * 	For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].
44 * 	
45 * 		The stable subarrays are [2], [2], and [2, 2]. The total number of stable subarrays is 3.
46 * 	
47 * 	
48 * 	For queries[1] = [0, 0], the subarray is [nums[0]] = [2].
49 * 	
50 * 		The stable subarray is [2]. The total number of stable subarrays is 1.
51 * 	
52 * 	
53 * 
54 * Thus, ans = [3, 1].
55 * </div>
56 *  
57 * Constraints:
58 * 
59 * 	1 <= nums.length <= 10^5
60 * 	1 <= nums[i] <= 10^5
61 * 	1 <= queries.length <= 10^5
62 * 	queries[i] = [li, ri]
63 * 	0 <= li <= ri <= nums.length - 1
64 * 
65 */
66pub struct Solution {}
67
68// problem: https://leetcode.com/problems/count-stable-subarrays/
69// discuss: https://leetcode.com/problems/count-stable-subarrays/discuss/?currentPage=1&orderBy=most_votes&query=
70
71// submission codes start here
72
73impl Solution {
74    pub fn count_stable_subarrays(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
75        
76    }
77}
78
79// submission codes end
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_3748() {
87    }
88}
89