CF2184G.Nastiness of Segments

Andrey remembered that he has $n$ blocks numbered from $1$ to $n$. On the block with number $i$, there is initially an integer $a_i$ written. He arranged them in a row in increasing order of their numbers: first is the block with number $1$, then the block with number $2$, and so on, with the block with number $n$ at the end.

For a certain segment of consecutive blocks $[l, r]$ ($1 \le l \le r \le n$), we call an integer $d\ (0 \le d \le r-l)$ nasty if $\min(a_l, a_{l+1}, \ldots, a_{l+d}) = d$.

Andrey is very curious, so he wants to perform $q$ operations of one of two types:

1. Change the number $a_i$ written on the $i$-th block to $x$.
2. Determine the nastiness of the segment $[l,\ r]\ (1 \le l \le r \le n)$. The nastiness of the segment refers to the number of nasty numbers $d\ (0 \le d \le r-l)$ for the given segment.

Andrey couldn't figure out how to process these queries quickly, so he turned to you for help. Help him perform the actions described above!

安德烈记得自己有 $n$ 个编号从 $1$ 到 $n$ 的方块。在编号为 $i$ 的方块上，初始时写有一个整数 $a_i$。他将这些方块按编号升序排成一行：最前面是编号为 $1$ 的方块，接着是编号为 $2$ 的方块，依此类推，最后是编号为 $n$ 的方块。

对于某个连续的方块区间 $[l, r]$（其中 $1 \le l \le r \le n$），若整数 $d$（满足 $0 \le d \le r-l$）使得

$$\min(a_l, a_{l+1}, \ldots, a_{l+d}) = d,$$

则称 $d$ 是“讨厌的”（nasty）。

安德烈非常好奇，因此他希望执行 $q$ 次操作，每次操作为以下两种类型之一：

1. 将第 $i$ 个方块上的数 $a_i$ 修改为 $x$；
2. 查询区间 $[l,\ r]$（其中 $1 \le l \le r \le n$）的“讨厌度”（nastiness）。该区间讨厌度定义为：满足上述条件的讨厌整数 $d$（$0 \le d \le r-l$）的个数。

安德烈无法快速处理这些查询，于是向你求助。请帮助他完成上述操作！

The first line contains an integer $t$ $(1 \le t \le 10^4)$ — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ $(1 \le n, q \le 2 \cdot 10^5)$ — the number of blocks and the number of operations, respectively.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 2 \cdot 10^5)$ — the initial numbers written on the blocks.

The following $q$ lines describe the operations to be performed.

Each line starts with an integer $idx$ $(1 \le idx \le 2)$ — the type of operation.

If $idx = 1$, then two integers $i$ $(1 \le i \le n)$ and $x$ $(1 \le x \le 2 \cdot 10^5)$ follow — the description of the first type of operation.

If $idx = 2$, then two integers $l$ and $r$ $(1 \le l \le r \le n)$ follow — the description of the second type of operation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）—— 分别表示方块的数量和操作的数量。

下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2 \cdot 10^5$）—— 表示方块上初始写下的数字。

接下来的 $q$ 行描述将要执行的操作。

每行以一个整数 $idx$（$1 \le idx \le 2$）开头—— 表示操作类型。

若 $idx = 1$，则随后是两个整数 $i$（$1 \le i \le n$）和 $x$（$1 \le x \le 2 \cdot 10^5$）—— 描述第一类操作。

若 $idx = 2$，则随后是两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）—— 描述第二类操作。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，且所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

For each test case, for each operation of the second type, print an integer representing the nastiness of the segment.

对于每个测试用例，针对每种第二类操作，输出一个整数，表示该区间的“恶劣度”。