You are given an integer array nums of length n and a 2D integer array queries.
A nums[i..j] is called a peak subarray if:
k such that i < k < j and:
nums[k] > nums[k - 1]nums[k] > nums[k + 1]You have to process queries of two types:
[1, li, ri]: Calculate the number of peak subarrays fully contained within nums[li..ri].[2, indexi, vali]: Update nums[indexi] to vali. This update applies to all subsequent queries.Return an array answer, where answer[i] is the answer to the ith query of type 1 in the order they appear.
Example 1:
Input: nums = [1,3,2,4], queries = [[1,0,3],[2,1,1],[1,0,3]]
Output: [2,0]
Explanation:
[1, 0, 3]:
[1, 3, 2]: choose k = 1. Then nums[k] = 3, nums[k - 1] = 1, and nums[k + 1] = 2. Since 3 > 1 and 3 > 2, this is a peak subarray.[1, 3, 2, 4]: choose k = 1. Then nums[k] = 3, nums[k - 1] = 1, and nums[k + 1] = 2. Since 3 > 1 and 3 > 2, this is a peak subarray.[2, 1, 1]: Update nums[1] to 1. The array becomes [1, 1, 2, 4].[1, 0, 3]: There are no peak subarrays now.answer = [2, 0].Example 2:
Input: nums = [9,8,9,8], queries = [[1,1,3],[2,2,1],[1,0,2]]
Output: [1,0]
Explanation:
[1, 1, 3]:
nums[1..3] = [8, 9, 8]: choose k = 2. Then nums[k] = 9, nums[k - 1] = 8, and nums[k + 1] = 8. Since 9 > 8 and 9 > 8, this is a peak subarray.[2, 2, 1]: Update nums[2] to 1. The array becomes [9, 8, 1, 8].[1, 0, 2]: There are no peak subarrays.answer = [1, 0].Example 3:
Input: nums = [3,6,2,7,1], queries = [[1,1,3],[2,3,0],[1,0,4]]
Output: [0,3]
Explanation:
[1, 1, 3]: The only subarray of length at least 3 is [6, 2, 7]. Its only possible peak index is k = 2, but nums[2] = 2 is less than both nums[1] = 6 and nums[3] = 7, so it is not a peak subarray.[2, 3, 0]: Update nums[3] to 0. The array becomes [3, 6, 2, 0, 1].[1, 0, 4]:
[3, 6, 2]: choose k = 1. Then nums[k] = 6, nums[k - 1] = 3, and nums[k + 1] = 2. Since 6 > 3 and 6 > 2, this is a peak subarray.[3, 6, 2, 0]: choose k = 1. Then nums[k] = 6, nums[k - 1] = 3, and nums[k + 1] = 2. Since 6 > 3 and 6 > 2, this is a peak subarray.[3, 6, 2, 0, 1]: choose k = 1. Then nums[k] = 6, nums[k - 1] = 3, and nums[k + 1] = 2. Since 6 > 3 and 6 > 2, this is a peak subarray.answer = [0, 3].
Constraints:
3 <= n == nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i] = [1, li, ri] or queries[i] = [2, indexi, vali]0 <= li < ri <= n - 10 <= indexi <= n - 10 <= vali <= 105