给你一个长度为 n 的整数数组 nums 和一个二维整数数组 queries。
如果满足以下条件,子数组 nums[i..j] 被称为 峰值子数组:
k 使得 i < k < j 且:
nums[k] > nums[k - 1]nums[k] > nums[k + 1]你需要处理以下两种类型的查询:
[1, li, ri]:计算完全包含在 nums[li..ri] 中的 峰值子数组 的数量。[2, indexi, vali]:将 nums[indexi] 更新为 vali。此更新适用于所有后续查询。返回一个数组 answer,其中 answer[i] 是按出现顺序排列的第 i 个类型 1 查询的答案。
子数组 是数组中连续的 非空 元素序列。
示例 1:
输入: nums = [1,3,2,4], queries = [[1,0,3],[2,1,1],[1,0,3]]
输出: [2,0]
解释:
[1, 0, 3]:
[1, 3, 2]:选择 k = 1。则 nums[k] = 3,nums[k - 1] = 1,且 nums[k + 1] = 2。因为 3 > 1 且 3 > 2,这是一个峰值子数组。[1, 3, 2, 4]:选择 k = 1。则 nums[k] = 3,nums[k - 1] = 1,且 nums[k + 1] = 2。因为 3 > 1 且 3 > 2,这是一个峰值子数组。[2, 1, 1]:将 nums[1] 更新为 1。数组变为 [1, 1, 2, 4]。[1, 0, 3]:现在没有峰值子数组。answer = [2, 0]。示例 2:
输入: nums = [9,8,9,8], queries = [[1,1,3],[2,2,1],[1,0,2]]
输出: [1,0]
解释:
[1, 1, 3]:
nums[1..3] = [8, 9, 8]:选择 k = 2。则 nums[k] = 9,nums[k - 1] = 8,且 nums[k + 1] = 8。因为 9 > 8 且 9 > 8,这是一个峰值子数组。[2, 2, 1]:将 nums[2] 更新为 1。数组变为 [9, 8, 1, 8]。[1, 0, 2]:没有峰值子数组。answer = [1, 0]。示例 3:
输入: nums = [3,6,2,7,1], queries = [[1,1,3],[2,3,0],[1,0,4]]
输出: [0,3]
解释:
[1, 1, 3]:唯一长度至少为 3 的子数组是 [6, 2, 7]。其唯一可能的峰值下标是 k = 2,但 nums[2] = 2 小于 nums[1] = 6 和 nums[3] = 7,因此它不是一个峰值子数组。[2, 3, 0]:将 nums[3] 更新为 0。数组变为 [3, 6, 2, 0, 1]。[1, 0, 4]:
[3, 6, 2]:选择 k = 1。则 nums[k] = 6,nums[k - 1] = 3,且 nums[k + 1] = 2。因为 6 > 3 且 6 > 2,这是一个峰值子数组。[3, 6, 2, 0]:选择 k = 1。则 nums[k] = 6,nums[k - 1] = 3,且 nums[k + 1] = 2。因为 6 > 3 且 6 > 2,这是一个峰值子数组。[3, 6, 2, 0, 1]:选择 k = 1。则 nums[k] = 6,nums[k - 1] = 3,且 nums[k + 1] = 2。因为 6 > 3 且 6 > 2,这是一个峰值子数组。answer = [0, 3]。
提示:
3 <= n == nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i] = [1, li, ri] 或 queries[i] = [2, indexi, vali]0 <= li < ri <= n - 10 <= indexi <= n - 10 <= vali <= 105