特殊的积木

题目描述

小蓝有 $n$ 个积木，从左到右编号为 $1$ 到 $n$。在第 $i$ 个积木上写着一个整数 $a_i$。

对于一个连续的积木段 $[l, r]$（$1 \le l \le r \le n$），我们定义一个整数 $d$（$0 \le d \le r-l$）是"特殊的"，如果从第 $l$ 个积木开始的连续 $d+1$ 个积木上数字的最小值恰好等于 $d$，即 $\min(a_l, a_{l+1}, \ldots, a_{l+d}) = d$。

小蓝想要进行 $q$ 次操作，操作有两种类型：

1. 修改操作：将第 $i$ 个积木上的数字改为 $x$。
2. 查询操作：查询积木段 $[l, r]$ 的"特殊度"，即该区间内特殊数的个数。

请帮助小蓝完成这些操作。

输入格式

第一行包含两个整数 $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$ 行，每行描述一个操作：

• 若第一个整数为 $1$，则后面跟着两个整数 $i$（$1 \le i \le n$）和 $x$（$1 \le x \le 2 \cdot 10^5$），表示修改操作。
• 若第一个整数为 $2$，则后面跟着两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示查询操作。

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

输出格式

对于每个测试用例，对于每次查询操作，输出一行一个整数，表示该区间的特殊度。

输入输出样例

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

1
0

3 2
1 1 1
2 1 3
2 1 2

1
1

说明/提示

对于 $40\%$ 的测试点，保证 $1\leq n\leq 500$。

对于所有测试点，保证 $1\leq n\leq 2\cdot10^5$。

在第一个样例中，初始积木为 $[1, 2, 3, 4, 5]$。

第一次查询 $[1, 5]$ 时：

• $d = 0$：$\min(1) = 1 \neq 0$，不是特殊的
• $d = 1$：$\min(1, 2) = 1 = 1$，是特殊的
• $d = 2$：$\min(1, 2, 3) = 1 \neq 2$，不是特殊的
• $d = 3$：$\min(1, 2, 3, 4) = 1 \neq 3$，不是特殊的
• $d = 4$：$\min(1, 2, 3, 4, 5) = 1 \neq 4$，不是特殊的

因此特殊度为 $1$。

经过修改后，积木变为 $[5, 5, 1, 4, 5]$，此时特殊度为 $0$。