3420. Count Non-Decreasing Subarrays After K Operations Hard

1/**
2 * [3420] Count Non-Decreasing Subarrays After K Operations
3 *
4 * You are given an array nums of n integers and an integer k.
5 * For each subarray of nums, you can apply up to k operations on it. In each operation, you increment any element of the subarray by 1.
6 * Note that each subarray is considered independently, meaning changes made to one subarray do not persist to another.
7 * Return the number of subarrays that you can make non-decreasing ​​​​​after performing at most k operations.
8 * An array is said to be non-decreasing if each element is greater than or equal to its previous element, if it exists.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [6,3,1,2,4,4], k = 7</span>
13 * Output: <span class="example-io">17</span>
14 * Explanation:
15 * Out of all 21 possible subarrays of nums, only the subarrays [6, 3, 1], [6, 3, 1, 2], [6, 3, 1, 2, 4] and [6, 3, 1, 2, 4, 4] cannot be made non-decreasing after applying up to k = 7 operations. Thus, the number of non-decreasing subarrays is 21 - 4 = 17.
16 * </div>
17 * <strong class="example">Example 2:
18 * <div class="example-block">
19 * Input: <span class="example-io">nums = [6,3,1,3,6], k = 4</span>
20 * Output: <span class="example-io">12</span>
21 * Explanation:
22 * The subarray [3, 1, 3, 6] along with all subarrays of nums with three or fewer elements, except [6, 3, 1], can be made non-decreasing after k operations. There are 5 subarrays of a single element, 4 subarrays of two elements, and 2 subarrays of three elements except [6, 3, 1], so there are 1 + 5 + 4 + 2 = 12 subarrays that can be made non-decreasing.
23 * </div>
24 *  
25 * Constraints:
26 * 
27 * 	1 <= nums.length <= 10^5
28 * 	1 <= nums[i] <= 10^9
29 * 	1 <= k <= 10^9
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/count-non-decreasing-subarrays-after-k-operations/
35// discuss: https://leetcode.com/problems/count-non-decreasing-subarrays-after-k-operations/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn count_non_decreasing_subarrays(nums: Vec<i32>, k: i32) -> i64 {
41        
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_3420() {
53    }
54}
55