可修改序列的单调栈¶

时间限制：0.5 秒。内存限制：256 MiB。参考评测环境与性能。

背景故事¶

观测站按位置记录信号强度。回放一段记录时，新信号会替换栈顶所有不比它强的信号。记录随时可能被修正，系统需要报告每次回放后留下多少条信号。

(本故事由GPT-6重写)

给定长度为 \(n\) 的整数序列 \(a\) ，处理 \(m\) 个操作：

1 x v ：令 \(a_x=v\) .
2 l r ：新建一个空栈，按 \(a_l,a_{l+1},\ldots,a_r\) 的顺序逐个加入。加入 \(v\) 前，只要栈非空且栈顶值 \(\le v\) ，就弹出栈顶；然后将 \(v\) 压栈。输出最终栈大小。

查询不修改序列。下标从 \(1\) 开始，每次查询都从空栈开始。相等元素会触发弹栈，栈内元素从底到顶严格递减。

第一行包含 n m ，第二行包含 \(n\) 个初始值。接下来 \(m\) 行，每行是上述一种操作。

每个查询输出一行一个整数。

1 3
0
2 1 1
1 1 1000000000
2 1 1

1
1

样例1的第一次查询留下 \([5,4,2]\) .修改首项后留下 \([4,2]\) ；查询两个相等的 \(3\) 只留下一个。

从左到右压栈，右侧不小于当前元素的值会将其移除。

\(1\le n,m\le50000\) ，\(0\le a_i,v\le10^9\) ，\(1\le x\le n\) ，\(1\le l\le r\le n\) .

规格重新设计：Codex（GPT-6）；明确遍历方向、相等时弹栈及每次查询的独立性。