#216576. [EGOI 2026] 给花浇水 / Watering Plants

在 Cesenatico 有一栋高楼，共有 层，每层住着一位居民。楼层从下往上编号为 到 ，居民 住在第 层。

每层楼都有一个阳台，居民们可以在那儿晒晒太阳，顺便种点花。他们还能顺便欣赏楼下阳台的花。由于所有的花每天都得浇水，大家决定互相帮助。每位居民都可以帮住在楼下那一层的居民浇水。

每天早上，所有居民都在时间 0 点离开大楼。起初，居民 回家的时间是 。如果居民 回家的时间严格早于住在楼下的那一位，即 ，那么居民 就会帮居民 浇花。（否则，居民 就得自己浇花。）每天结束时，会发生以下两种事件之一：

• 类型 !：某位居民 更新了他们回家的时间，从隔天开始生效。
• 类型 ?：某位居民 询问他们已经帮居民 浇了多少次花。

注意：居民 不会帮任何人浇花，而居民 的花也永远不会被别人浇。

你的任务是帮居民们回答所有 ? 类型的询问。

第一行包含两个整数 和 ，分别代表居民人数和需要追踪的天数。

下一行包含 个整数 ，这是每位居民最初回家的时间。

接下来有 行，第 行描述了第 天结束时发生的事件。

每个事件格式如下：

• ! r x。居民 () 从隔天开始在时间 回家，也就是说 的值变为 。注意， 有可能和当前的 相同。
• ? r。询问居民 () 自第 天开始以来，一共帮居民 浇了多少次花。

保证至少有一个 ? 事件。

对于每个 ? 事件，输出一行一个整数：即自第 天开始，居民 帮居民 浇花的次数。

注意：在这个问题中，不要算上居民自己给自己浇花的次数。

样例输入 1

3 4
7 7 5
? 2
? 1
? 2
? 2

样例输出 1

1
0
3
4

样例输入 2

2 5
5 7
! 1 4
? 1
! 0 4
! 1 6
? 1

样例输出 2

1
2

样例输入 3

4 6
13 9 15 2
! 1 18
? 3
! 0 12
! 2 1
? 1
? 2

样例输出 3

2
1
5

样例输入 4

3 6
5 2 4
? 1
! 1 8
! 0 10
! 1 3
? 1
? 2

样例输出 4

1
4
2

样例解释

:::align{center}

样例 1。喷壶图标表示该居民会帮楼下邻居浇花。 :::

第一个样例适用于子任务 2、4、5 和 6。由于日程从未更新，居民 每天都比居民 早回家，并帮他们浇花。第 天后，居民 帮邻居浇了一次花。由于居民 和 在同一时间回家，居民 不会帮居民 浇花。第 天后，居民 仍然没有帮邻居浇过花。第 天后，居民 帮邻居浇了三次花。第 天后，居民 帮邻居浇了四次花。

:::align{center}

样例 2。 :::

第二个样例适用于子任务 3、4 和 6。在第 天，居民 没有帮邻居浇花。第 天后，居民 的日程更新了。由于在第 天他们比邻居更早回家，所以他们帮邻居浇了花。第 天后，居民 帮邻居浇了一次花。在第 天，居民 再次帮邻居浇了花。第 天后，居民 总共帮邻居浇了两次花。

第三个样例适用于子任务 4、5 和 6。注意此示例没有插图。

:::align{center}

样例 4。 :::

第四个样例适用于子任务 4 和 6。第 天后，居民 帮邻居浇了一次花。第 天后，居民 帮邻居浇了四次花（分别在第 、第 、第 和第 天）。居民 总共帮邻居浇了两次花（在第 和第 天）。

约束条件

• .
• .
• （最初以及每次变动后）。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 [ 分]: 样例。
• 子任务 [ 分]: ，即只有一个 ? 类型的事件。
• 子任务 [ 分]: 所有事件都是 ? 类型。
• 子任务 [ 分]: 。
• 子任务 [ 分]: 且 。
• 子任务 [ 分]: 每位居民最多更改一次回家时间。
• 子任务 [ 分]: 没有额外的约束条件。