题目描述

有 $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 函数。

你应当实现以下的函数：

vector<long long> tower_events(vector<int> H, vector<vector<int>> 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 5
1 2 3 4 5
1 0
2 1 3
3 1 2 1
1 1
2 0 4

3
6

10 11
7 7 9 5 8 10 2 9 2 2
1 1
3 6 8 6
1 1
2 1 9
1 3
1 8
2 2 4
1 5
3 1 1 7
1 1
2 0 9

5
3
10

提示

数据范围

• $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$

考虑以下调用：

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$

考虑以下调用：

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]$。