<p>A <strong>peak</strong> in an array <code>arr</code> is an element that is <strong>greater</strong> than its previous and next element in <code>arr</code>.</p>

<p>You are given an integer array <code>nums</code> and a 2D integer array <code>queries</code>.</p>

<p>You have to process queries of two types:</p>

<ul>
	<li><code>queries[i] = [1, l<sub>i</sub>, r<sub>i</sub>]</code>, determine the count of <strong>peak</strong> elements in the <span data-keyword="subarray">subarray</span> <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.<!-- notionvc: 73b20b7c-e1ab-4dac-86d0-13761094a9ae --></li>
	<li><code>queries[i] = [2, index<sub>i</sub>, val<sub>i</sub>]</code>, change <code>nums[index<sub>i</sub>]</code> to <code><font face="monospace">val<sub>i</sub></font></code>.</li>
</ul>

<p>Return an array <code>answer</code> containing the results of the queries of the first type in order.<!-- notionvc: a9ccef22-4061-4b5a-b4cc-a2b2a0e12f30 --></p>

<p><strong>Notes:</strong></p>

<ul>
	<li>The <strong>first</strong> and the <strong>last</strong> element of an array or a subarray<!-- notionvc: fcffef72-deb5-47cb-8719-3a3790102f73 --> <strong>cannot</strong> be a peak.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,1,4,2,5], queries = [[2,3,4],[1,0,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0]</span></p>

<p><strong>Explanation:</strong></p>

<p>First query: We change <code>nums[3]</code> to 4 and <code>nums</code> becomes <code>[3,1,4,4,5]</code>.</p>

<p>Second query: The number of peaks in the <code>[3,1,4,4,5]</code> is 0.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [4,1,4,2,1,5], queries = [[2,2,4],[1,0,2],[1,0,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0,1]</span></p>

<p><strong>Explanation:</strong></p>

<p>First query: <code>nums[2]</code> should become 4, but it is already set to 4.</p>

<p>Second query: The number of peaks in the <code>[4,1,4]</code> is 0.</p>

<p>Third query: The second 4 is a peak in the <code>[4,1,4,2,1]</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i][0] == 1</code> or <code>queries[i][0] == 2</code></li>
	<li>For all <code>i</code> that:
	<ul>
		<li><code>queries[i][0] == 1</code>: <code>0 &lt;= queries[i][1] &lt;= queries[i][2] &lt;= nums.length - 1</code></li>
		<li><code>queries[i][0] == 2</code>: <code>0 &lt;= queries[i][1] &lt;= nums.length - 1</code>, <code>1 &lt;= queries[i][2] &lt;= 10<sup>5</sup></code></li>
	</ul>
	</li>
</ul>

import math
from typing import *
from pprint import pprint
from functools import cache
import collections
from copy import deepcopy
import heapq
from queue import PriorityQueue

MOD = 10 ** 9 + 7
P = 256

class SegmentTreeRecursive:

    def __init__(self, size):
        self.tree = [0] * (4 * size) # Requires 4 time if size in recursive implementation
        self.size = size


    def query(self,qs,qe):
        return self.query_helper(1,0,self.size - 1, qs,qe)

    def query_helper(self, node_idx, start, end, left, right):

        if left > end or right < start:
            return 0
        if left <= start and end <= right:
            return self.tree[node_idx]

        left_node_idx, right_node_idx = 2*node_idx , 2*node_idx + 1
        mid = (start + end)//2
        return (self.query_helper(left_node_idx, start, mid, left, right) +
                self.query_helper(right_node_idx, mid + 1, end, left, right))

    def update(self, qs, qe, val):
        self.update_helper(1, 0, self.size - 1, qs, qe,val)

    def update_helper(self, node_idx, start, end, left, right, val):
        if left > end or right < start:
            return 0
        if (left <= start and end <= right) and (start == end):
            self.tree[node_idx] = val
        else:
            left_node_idx, right_node_idx = 2*node_idx , 2*node_idx + 1
            mid = (start + end)//2
            self.update_helper(left_node_idx, start, mid, left, right, val)
            self.update_helper(right_node_idx, mid + 1, end, left, right, val)
            self.tree[node_idx] = self.tree[left_node_idx] + self.tree[right_node_idx]

class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        st = SegmentTreeRecursive(n)
        # print("nums = ", nums)
        for i in range(1,n-1):
            if nums[i-1] < nums[i] and nums[i + 1] < nums[i]:
                st.update(i,i,1)
        # print(st.tree)
        res = []

        def check_and_update(idx):
            if idx == 0 or idx == n - 1:
                st.update(idx, idx, 0)
            elif nums[idx - 1] < nums[idx] and nums[idx + 1] < nums[idx]:
                st.update(idx, idx, 1)
            else:
                st.update(idx, idx ,0)
        for query in queries:
            if query[0] == 1:
                _,l,r = query
                if l == r:
                    res.append(0)
                else:
                    res.append(st.query(l + 1,r - 1))
            else:
                _,idx,val = query
                nums[idx] = val
                if idx == 0:
                    check_and_update(idx + 1)
                elif idx == n - 1:
                    check_and_update(idx - 1)
                else:
                    if nums[idx] > nums[idx + 1] and nums[idx] > nums[idx - 1]:
                        st.update(idx + 1, idx + 1, 0)
                        st.update(idx - 1, idx - 1, 0)
                        st.update(idx,idx,1)
                    else:
                        # print(idx)
                        st.update(idx, idx, 0)
                        # print("updated = ", st.tree)
                        if nums[idx] >= nums[idx + 1]:
                            st.update(idx + 1, idx + 1, 0)
                        else:
                            check_and_update(idx + 1)

                        if nums[idx] >= nums[idx - 1]:
                            st.update(idx - 1, idx - 1, 0)
                        else:
                            check_and_update(idx - 1)
            # print(nums)
        return res

78400