题目描述

Andrey 记得自己有 $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$）是“nasty”的，如果 $\min(a_l, a_{l+1}, \ldots, a_{l+d}) = d$。

Andrey 很好奇，所以他想要进行 $q$ 次两种类型的操作之一：

1. 将第 $i$ 个方块上的数字 $a_i$ 改成 $x$。
2. 查询区间 $[l, r]$（$1 \le l \le r \le n$）的 nastiness，其中“nastiness”指的是该区间内“nasty”数 $d$（$0 \le d \le r-l$）的个数。

Andrey 不知道如何快速处理这些操作，因此他向你求助。请你帮助他完成上述操作！

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，对于每一个第二类型的操作，输出一个整数，表示该区间的 nastiness。

样例

1
5 5
1 2 3 4 5
2 1 5
1 1 5
1 2 5
1 3 1
2 1 5

1
0

样例说明

由 ChatGPT 5 翻译

来源

Codeforces 2184G，英文题名 Nastiness of Segments。