<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>

class SegTree:
    def __init__(self, nums):
        self.nums = nums
        self.nodes = [0] * (4 * len(nums))
        self._build_tree(0, 0, len(nums) - 1)
    
    def _build_tree(self, node, lo, hi):
        if lo == hi:
            self._check_peak(node, lo)
        else:
            mid = (lo + hi) // 2
            self.nodes[node] = self._build_tree(2 * node + 1, lo, mid) + \
                self._build_tree(2 * node + 2, mid + 1, hi)
        return self.nodes[node]
    
    def _check_peak(self, node, idx):
        left = idx > 0 and self.nums[idx] > self.nums[idx - 1]
        right = idx < len(self.nums) - 1 and self.nums[idx] > self.nums[idx + 1]
        self.nodes[node] = 1 if left and right else 0

    def _find_node(self, idx):
        node, lo, hi = 0, 0, len(self.nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if idx <= mid:
                node = 2 * node + 1
                hi = mid
            else:
                node = 2 * node + 2
                lo = mid + 1
        return node
    
    def _update_parents(self, node):
        while node > 0:
            parent = (node - 1) // 2
            self.nodes[parent] = self.nodes[2 * parent + 1] + \
                self.nodes[2 * parent + 2]
            node = parent
    
    def update(self, idx, val):
        self.nums[idx] = val
        for i in (idx - 1, idx, idx + 1):
            if 0 <= i < len(self.nums):
                node = self._find_node(i)
                self._check_peak(node, i)
                self._update_parents(node)
    
    def query(self, l, r):
        if l > r:
            return 0
        def helper(node, lo, hi):
            if l <= lo and hi <= r:
                return self.nodes[node]
            if hi < l or lo > r:
                return 0
            mid = (lo + hi) // 2
            return helper(2 * node + 1, lo, mid) + \
                helper(2 * node + 2, mid + 1, hi)
        return helper(0, 0, len(self.nums) - 1)
    
    def _print_nodes(self):
        def helper(node, lo, hi, depth):
            print('\t' * depth + f'[{lo},{hi}] - {self.nodes[node]}')
            if lo < hi:
                mid = (lo + hi) // 2
                helper(2 * node + 1, lo, mid, depth + 1)
                helper(2 * node + 2, mid + 1, hi, depth + 1)
        helper(0, 0, len(self.nums) - 1, 0)
        print()

class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        tree = SegTree(nums)
        ans = []
        for qtype, arg1, arg2 in queries:
            if qtype == 1:
                ans.append(tree.query(arg1 + 1, arg2 - 1))
            else:
                tree.update(arg1, arg2)
        return ans
83000