statement.zh.md

可修改序列的单调栈

时间限制：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

输入

5 6
5 3 3 4 2
2 1 5
1 1 1
2 1 5
2 2 3
1 3 8
2 2 5

输出

3
2
1
3

样例 2

输入

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）；明确遍历方向、相等时弹栈及每次查询的独立性。

分值	额外限制
20%	$n\le50,\ m\le100$
30%	$n,m\le2000$
50%	无额外限制