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

from typing import TypeVar, List

T = TypeVar('T')


class SegmentTree:
    def __init__(self, arr: list[T]):
        self.n = len(arr)
        self.t: list[T] = [None] * (4 * len(arr))
        self.arr = arr
        self.build(0, 0, len(arr) - 1)

    def merge(self, node1: tuple[int, int, tuple[int, int | None], tuple[int | None, int]],
              node2: tuple[int, int, tuple[int, int | None], tuple[int | None, int]]) -> tuple[
        int, int, tuple[int, int], tuple[int, int]]:

        if node1 is None:
            return node2

        if node2 is None:
            return node1

        num_p1, num_els1, first_el1, last_el1 = node1
        num_p2, num_els2, first_el2, last_el2 = node2
        add_1 = 0
        add_2 = 0

        if None not in last_el1:
            if last_el1[1] > last_el1[0] and last_el1[1] > first_el2[0]:
                add_1 = 1
        if None not in first_el2:
            if first_el2[0] > last_el1[1] and first_el2[0] > first_el2[1]:
                add_2 = 1

        if first_el1[1] is None:
            first_el1 = first_el1[0], first_el2[0]

        if last_el2[0] is None:
            last_el2 = last_el1[1], last_el2[1]

        return num_p1 + num_p2 + add_1 + add_2, num_els1 + num_els2, first_el1, last_el2,

    def build(self, v: int, tl: int, tr: int):
        if tl == tr:
            self.t[v] = (0, 1, (self.arr[tl], None,), (None, self.arr[tl],))  # num peaks, num els, first el, last el
        else:
            tm = (tl + tr) // 2
            self.build(2 * v + 1, tl, tm)
            self.build(2 * v + 2, tm + 1, tr)
            self.t[v] = self.merge(self.t[2 * v + 1], self.t[2 * v + 2])

    def query(self, l: int, r: int) -> T:
        """
        Query for sum could be anything
        """

        def _query(v, tl, tr, l, r):

            if l > r:
                return None

            if tl == l and tr == r:
                return self.t[v]

            tm = (tl + tr) // 2
            return self.merge(_query(2 * v + 1, tl, tm, l, min(r, tm)),
                              _query(2 * v + 2, tm + 1, tr, max(tm + 1, l), r))

        return _query(0, 0, self.n - 1, l, r)[0]

    def update(self, pos, new_val):
        def _update(v, tl, tr):
            if tl == tr:
                self.t[v] = (0, 1, (new_val, None,), (None, new_val,))
                return
            tm = (tl + tr) // 2

            if pos <= tm:
                _update(2 * v + 1, tl, tm)
            else:
                _update(2 * v + 2, tm + 1, tr)
            self.t[v] = self.merge(self.t[2 * v + 1], self.t[2 * v + 2])

        _update(0, 0, self.n - 1)
        self.arr[pos] = new_val


class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        st = SegmentTree(nums)
        res = []
        for type, i, j in queries:
            if type == 1:
                res.append(st.query(i, j))
            else:
                st.update(i, j)

        return res
92000