P16543 [EGOI 2026] 给花浇水 / Watering Plants

在 Cesenatico 有一栋高楼，共有 $N$ 层，每层住着一位居民。楼层从下往上编号为 $0$ 到 $N - 1$，居民 $r$ 住在第 $r$ 层。 每层楼都有一个阳台，居民们可以在那儿晒晒太阳，顺便种点花。他们还能顺便欣赏楼下阳台的花。由于所有的花每天都得浇水，大家决定互相帮助。每位居民都可以帮住在楼下那一层的居民浇水。 每天早上，所有居民都在时间 0 点离开大楼。起初，居民 $r$ 回家的时间是 $t_r$。如果居民 $r$ 回家的时间严格早于住在楼下的那一位，即 $t_r < t_(r - 1)$，那么居民 $r$ 就会帮居民 $r - 1$ 浇花。（否则，居民 $r - 1$ 就得自己浇花。）每天结束时，会发生以下两种事件之一： - **类型** `!`：某位居民 $r$ 更新了他们回家的时间，从隔天开始生效。 - **类型** `?`：某位居民 $r$ 询问他们已经帮居民 $r - 1$ 浇了多少次花。 注意：居民 $0$ 不会帮任何人浇花，而居民 $N - 1$ 的花也永远不会被别人浇。 你的任务是帮居民们回答所有 `?` 类型的询问。

第一行包含两个整数 $N$ 和 $D$，分别代表居民人数和需要追踪的天数。 下一行包含 $N$ 个整数 $t_0, t_1, \cdots, t_{N-1}$，这是每位居民最初回家的时间。 接下来有 $D$ 行，第 $i$ 行描述了第 $i$ 天结束时发生的事件。 每个事件格式如下： - `! r x`。居民 $r$ ($0 \leq r \leq N-1$) 从隔天开始在时间 $x$ 回家，也就是说 $t_r$ 的值变为 $x$。注意，$x$ 有可能和当前的 $t_r$ 相同。 - `? r`。询问居民 $r$ ($1 \leq r \leq N-1$) 自第 $0$ 天开始以来，一共帮居民 $r - 1$ 浇了多少次花。 保证至少有一个 `?` 事件。

对于每个 `?` 事件，输出一行一个整数：即自第 $0$ 天开始，居民 $r$ 帮居民 $r - 1$ 浇花的次数。 注意：在这个问题中，不要算上居民自己给自己浇花的次数。

### 样例解释 :::align{center}  样例 1。喷壶图标表示该居民会帮楼下邻居浇花。 ::: 第一个样例适用于子任务 2、4、5 和 6。由于日程从未更新，居民 $2$ 每天都比居民 $1$ 早回家，并帮他们浇花。第 $0$ 天后，居民 $2$ 帮邻居浇了一次花。由于居民 $0$ 和 $1$ 在同一时间回家，居民 $1$ 不会帮居民 $0$ 浇花。第 $1$ 天后，居民 $1$ 仍然没有帮邻居浇过花。第 $2$ 天后，居民 $2$ 帮邻居浇了三次花。第 $3$ 天后，居民 $2$ 帮邻居浇了四次花。 :::align{center}  样例 2。 ::: 第二个样例适用于子任务 3、4 和 6。在第 $0$ 天，居民 $1$ 没有帮邻居浇花。第 $0$ 天后，居民 $1$ 的日程更新了。由于在第 $1$ 天他们比邻居更早回家，所以他们帮邻居浇了花。第 $1$ 天后，居民 $1$ 帮邻居浇了一次花。在第 $2$ 天，居民 $1$ 再次帮邻居浇了花。第 $4$ 天后，居民 $1$ 总共帮邻居浇了两次花。 第三个样例适用于子任务 4、5 和 6。注意此示例没有插图。 :::align{center}  样例 4。 ::: 第四个样例适用于子任务 4 和 6。第 $0$ 天后，居民 $1$ 帮邻居浇了一次花。第 $4$ 天后，居民 $1$ 帮邻居浇了四次花（分别在第 $0$、第 $1$、第 $3$ 和第 $4$ 天）。居民 $2$ 总共帮邻居浇了两次花（在第 $2$ 和第 $3$ 天）。 ### 约束条件 - $2 \leq N \leq 200\ 000$. - $1 \leq D \leq 200\ 000$. - $1 \leq t_r \leq 10^9$（最初以及每次变动后）。 ### 评分方式 你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。 - **子任务 $0$** [$0$ 分]: 样例。 - **子任务 $1$** [$9$ 分]: $D = 1$，即只有一个 ? 类型的事件。 - **子任务 $2$** [$12$ 分]: 所有事件都是 `?` 类型。 - **子任务 $3$** [$13$ 分]: $N = 2$。 - **子任务 $4$** [$18$ 分]: $N \le 2000$ 且 $D \le 2000$。 - **子任务 $5$** [$21$ 分]: 每位居民最多更改一次回家时间。 - **子任务 $6$** [$27$ 分]: 没有额外的约束条件。