P15589 [KTSC 2026] 瞭望塔 / Observation Tower

有 $N$ 座瞭望塔，依次编号 $0\sim N-1$。塔 $i$ 的高度为 $H[i]$，其瞭望分数为 $S[i]$。初始，$S[i]=0$。 对于 $0\le i\lt j\le N-1$，我们称塔 $j$ 能从塔 $i$ 瞭望到，当且仅当对于任意 $i\le k\le j-1$，都有 $H[k]\lt H[j]$。注意，$j\le i$ 时，塔 $j$ 不能从塔 $i$ 瞭望到。 当从某座塔上执行一次瞭望操作时，能从这座塔瞭望到的所有塔的瞭望分数都会自增 $1$。 现在有 $Q$ 个事件，每个事件是如下的三个类型之一： - **瞭望**：给定 $I$（$0\le I\le N-2$），在塔 $I$ 上执行一次瞭望操作。 - **测量**：给定 $L,R$（$0\le L\le R\le N-1$），计算 $S[L]+\cdots+S[R]$。 - **平移**：给定 $L,R,V$（$0\le L\le R\le N-1$）。对于任意 $L\le i\le R$，令 $H[i]\gets H[i]+V$ 瞭望事件用数组 $[I]$ 表示；测量事件用数组 $[L,R]$ 表示；平移事件用数组 $[L,R,V]$ 表示。注意到这三类事件的数组大小均不同，所以可以用数组大小区分不同的事件类型。 事件按照 $0\sim Q-1$ 的顺序依次发生，事件 $i$ 用 $E[i]$ 表示。 令测量事件总数为 $K$，按照发生顺序编号 $0\sim K-1$。求出所有测量事件的结果。 ### 实现细节 **这是一道函数式交互题**。你不必，也不应实现 `main` 函数。 你应当实现以下的函数： ```cpp vector tower_events(vector H, vector E) ``` - $H$：大小为 $N$ 的整数数组。 - $Q$：大小为 $Q$ 的整数数组，表示事件。 - 返回一个大小为 $K$ 的整数数组 $X$，其中 $X[i]$ 表示第 $i$ 个测量事件的结果。 - 该函数被调用恰好一次。

示例评分程序的输入格式如下： * 第 $1$ 行：$N$ $Q$ * 第 $2$ 行：$H[0]$ $H[1] \dots H[N - 1]$ * 对于所有 $0 \le i \le Q - 1$： * 第 $3 + i$ 行：$|E[i]|$ $E[i][0] \dots E[i][|E[i]| - 1]$

示例评分程序按以下格式输出答案： * 对于所有 $0 \le i \le K - 1$： * 第 $1 + i$ 行：$X[i]$

### 数据范围 - $5\le N\le 1\, 000\, 000$； - $1\le Q\le 250\, 000$； - $1\le H[i]\le 10^9$； - 对于瞭望事件，$0\le I\le N-2$； - 对于测量事件，$0\le L\le R\le N-1$； - 对于平移事件，$0\le L\le R\le N-1$，$-10^9\le V\le 10^9$； - 在平移事件发生后，保证 $H[i]\ge 1$； - 至少有一个测量事件。 ### 子任务 | 编号 | 得分 | 限制 | | :-: | :-: | :- | | $1$ | $17$ | $N,Q\le 150\, 000$；在所有测量事件中，$L=0,R=N-1$ | | $2$ | $ 6$ | $N,Q\le 150\, 000$；无平移事件 | | $3$ | $12$ | $N,Q\le 150\, 000$ | | $4$ | $19$ | 在所有瞭望事件中，$I=0$；在所有平移事件中，$L=R$；平移事件至多发生 $30\, 000$ 次 | | $5$ | $21$ | 在所有测量事件中，$L=R$；在所有平移事件中，$L=R$ 且 $V\ge 0$ | | $6$ | $25$ | 无额外限制 | ### 样例 #### 样例 $1$ 考虑以下调用： ```cpp tower_events([1, 2, 3, 4, 5], [[0], [1, 3], [1, 2, 1], [1], [0, 4]]) ``` * 在第一个事件之后，$H = [1, 2, 3, 4, 5]$，$S = [0, 1, 1, 1, 1]$。 * 第二个事件（即测量事件 $0$）的结果为 $S[1] + S[2] + S[3] = 3$。 * 在第三个事件之后，$H = [1, 3, 4, 4, 5]$，$S = [0, 1, 1, 1, 1]$。 * 在第四个事件之后，$H = [1, 3, 4, 4, 5]$，$S = [0, 1, 2, 1, 2]$。 * 最后一个事件（即测量事件 $1$）的结果为 $S[0] + \cdots + S[4] = 6$。 因此，该函数应返回 $[3, 6]$。 #### 样例 $2$ 考虑以下调用： ```cpp tower_events([7, 7, 9, 5, 8, 10, 2, 9, 2, 2], [[1], [6, 8, 6], [1], [1, 9], [3], [8], [2, 4], [5], [1, 1, 7], [1], [0, 9]]) ``` 该函数应返回 $[5, 3, 10]$。