1003. C. Stalin Sort

题目描述

给定一个长度为 (n) 的序列 (a_1,a_2,\ldots,a_n)，其中每个元素均为 (0,1,2) 中的一个。

对于当前序列的一个连续区间 ([L,R])，一次 斯大林排序操作 按照以下方式进行：

1. 从左到右扫描区间内的元素，第一个元素一定被保留；
2. 对于之后的元素 (a_i)，当且仅当

时保留它。特别地，等于当前前缀最大值的元素也会被保留；

3. 将所有未被保留的元素按照原相对顺序排列，再将所有被保留的元素按照原相对顺序接在其后，用得到的新序列替换原区间。

例如，对 2 2 1 0 2 进行一次整段操作，未保留部分为 1 0，保留部分为 2 2 2，操作后得到 1 0 2 2 2。

接下来处理 (q) 个操作：

• 1 p x：将 (a_p) 修改为 (x)；
• 2 l r：从当前的 (a_l,a_{l+1},\ldots,a_r) 出发，每次选择一个完全包含在 ([l,r]) 内的连续区间进行斯大林排序操作。询问至少需要多少次操作，才能使 (a_l,a_{l+1},\ldots,a_r) 非降。

第二类询问中的斯大林排序操作都是虚拟操作，不会真正修改序列。

样例解释

第一次询问的序列为 2 1 0 0 1 2，至少需要两次操作。

区间 ([3,6]) 为 0 0 1 2，已经非降，因此答案为 (0)。区间 ([2,5]) 为 1 0 0 1，操作一次即可变成 0 0 1 1。

第一组数据的最后一次询问中，当前序列为 0 0 0 2 1 0，答案重新变为 (2)。这也说明第二类询问本身不会修改序列。

第二组数据中，最初的两个 2 都会被保留，对整个区间操作一次即可得到 1 2 2。

数据范围

• (1\leq T\leq10)；
• (1\leq n,q\leq2\times10^5)；
• (a_i,x\in{0,1,2})；
• 对于所有测试数据，(n) 之和不超过 (4\times10^5)，(q) 之和不超过 (4\times10^5)；
• 修改操作满足 (1\leq p\leq n)；
• 询问操作满足 (1\leq l\leq r\leq n)。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 (n,q)；
• 第二行包含 (n) 个整数 (a_1,a_2,\ldots,a_n)；
• 接下来 (q) 行，每行包含三个整数，表示一次操作，格式与题目描述相同。

输出格式

对于每个第二类询问，输出一行一个整数，表示最少操作次数。

样例输入

2
6 10
2 1 0 0 1 2
2 1 6
2 3 6
2 2 5
1 1 0
2 1 6
1 2 0
2 1 6
1 4 2
1 6 0
2 1 6
3 5
2 2 1
2 1 3
1 3 0
2 1 3
1 2 1
2 1 3

样例输出

2
0
1
1
0
2
1
1
2

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1003