# 可修改序列的单调栈

时间限制：0.5 秒。内存限制：256 MiB。参考 [评测环境与性能](../../../docs/评测环境与性能.md)。

## 背景故事

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

(本故事由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

### 输入

```text
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
```

### 输出

```text
3
2
1
3
```

## 样例 2

### 输入

```text
1 3
0
2 1 1
1 1 1000000000
2 1 1
```

### 输出

```text
1
1
```

## 样例解释

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

![从左到右压栈，右侧不小于当前元素的值会将其移除。](assets/example.svg)

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

## 数据范围与保证

$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% | 无额外限制 |