← 返回题目列表

Codeforces · 2184/G

G. 片段的肮脏

中文机器翻译题面 查看原题

安德烈记得他有$$$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$$$。

Andrey 很好奇,所以他想执行以下两种类型之一的 $$$q$$$ 操作:

  1. 将第$$$i$$$块上写入的数字$$$a_i$$$更改为$$$x$$$。
  2. 确定 肮脏 段 $$$[l,\ r]\ (1 \le l \le r \le n)$$$ 的 。段的肮脏度是指给定段的肮脏数字 $$$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$$$。

输出

对于每个测试用例,对于第二类型的每个操作,打印一个表示该段的肮脏程度的整数。

示例

输入
复制

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