3187. Peaks in Array

Problem Link

Description

---

A peak in an array arr is an element that is greater than its previous and next element in arr.

You are given an integer array nums and a 2D integer array queries.

You have to process queries of two types:

• queries[i] = [1, li, ri], determine the count of peak elements in the subarray nums[li..ri].
• queries[i] = [2, indexi, vali], change nums[indexi] to vali.

Return an array answer containing the results of the queries of the first type in order.

Notes:

• The first and the last element of an array or a subarray cannot be a peak.

 

Example 1:

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

Output: [0]

Explanation:

First query: We change nums[3] to 4 and nums becomes [3,1,4,4,5].

Second query: The number of peaks in the [3,1,4,4,5] is 0.

Example 2:

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

Output: [0,1]

Explanation:

First query: nums[2] should become 4, but it is already set to 4.

Second query: The number of peaks in the [4,1,4] is 0.

Third query: The second 4 is a peak in the [4,1,4,2,1].

 

Constraints:

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i][0] == 1 or queries[i][0] == 2
• For all i that:
  • queries[i][0] == 1: 0 <= queries[i][1] <= queries[i][2] <= nums.length - 1
  • queries[i][0] == 2: 0 <= queries[i][1] <= nums.length - 1, 1 <= queries[i][2] <= 105

Solution

---

C++

const int MAXN = 100005;
 
class Solution {
public:
    int arr[MAXN];
    int t[4 * MAXN];
    
    void build(int a[], int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(a, v*2, tl, tm);
            build(a, v*2+1, tm+1, tr);
            t[v] = t[v*2] + t[v*2 + 1];
        }
    }
    
    void update(int v, int tl, int tr, int pos, int new_val) {
        if (tl == tr) {
            t[v] = new_val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update(v*2, tl, tm, pos, new_val);
            else
                update(v*2+1, tm+1, tr, pos, new_val);
            t[v] = t[v*2] + t[v*2+1];
        }
    }
 
    int query(int v, int tl, int tr, int l, int r) {
        if (l > r)
            return 0;
        if (l == tl && tr == r)
            return t[v];
        
        int tm = (tl + tr) / 2;
        return query(v*2, tl, tm, l, min(r, tm)) + query(v*2+1, tm+1, tr, max(l, tm+1), r);
    }
    
    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
        int N = nums.size();
        memset(arr, 0, sizeof arr);
        
        for (int i = 1; i < N - 1; i++) {
            arr[i] = nums[i] > nums[i - 1] && nums[i] > nums[i + 1];
        }
        
        vector<int> ans;
        build(arr, 1, 0, MAXN - 1);
 
        for (auto& q: queries) {
            if (q[0] == 1) {
                int v = query(1, 0, MAXN - 1, q[1] + 1, q[2] - 1);
                ans.push_back(v);
            } else {
                int index = q[1], val = q[2];
                nums[index] = val;
                
                for (int i = index - 1; i <= index + 1; i++) {
                    int count = (i > 0 && i < N - 1 && nums[i] > nums[i - 1] && nums[i] > nums[i + 1]);
                    if (i < nums.size() - 1 && count != arr[i]) {
                        update(1, 0, MAXN - 1, i, count);
                        arr[i] = count;
                    }
                }
            }
 
        }
        
        return ans;
    }
};

Python3

class SegmentTree:
	def __init__(self, arr):
		self.n = len(arr)
		self.tree = [0] * (4 * self.n)		
		self._build(1, 0, self.n - 1, arr)
 
	def _build(self, v, tl, tr, arr):
		if tl == tr:
			self.tree[v] = arr[tl]
		else:
			tm = tl + (tr - tl) // 2
			self._build(v * 2, tl, tm, arr)
			self._build(v * 2 + 1, tm + 1, tr, arr)
			self.tree[v] = self.tree[v * 2] + self.tree[v * 2 + 1]
 
	def query(self, v, tl, tr, l, r):
		if l > r: return 0
		
		if tl == l and tr == r:
			return self.tree[v]
		else:
			tm = tl + (tr - tl) // 2
			
			return self.query(v * 2, tl, tm, l, min(tm, r)) + self.query(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r)
 
	def update(self, v, tl, tr, pos, value):
		if tl == tr:
			self.tree[v] = value
		else:
			tm = tl + (tr - tl) // 2
 
			if pos <= tm:
				self.update(v * 2, tl, tm, pos, value)
			else:
				self.update(v * 2 + 1, tm + 1, tr, pos, value)
 
			self.tree[v] = self.tree[v * 2] + self.tree[v * 2 + 1]
            
class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        N = len(nums)
        isPeaked = [0] * N
        res = []
        
        def isPeak(j):
            return int(0 < j < N - 1 and nums[j] > nums[j - 1] and nums[j] > nums[j + 1])
        
        for i in range(1, N - 1):
            isPeaked[i] = isPeak(i)
        
        st = SegmentTree(isPeaked)
        
        for query in queries:
            if query[0] == 1:
                _, l, r = query
                v = st.query(1, 0, N - 1, l + 1, r - 1)
                res.append(v)
            else:
                _, index, val = query
                nums[index] = val
                
                for j in [index - 1, index, index + 1]:
                    count = isPeak(j)
                    if j < N and count != isPeaked[j]:
                        st.update(1, 0, N - 1, j, count)
                        isPeaked[j] = count
        
        return res