Problem Description

There are $N$ observation towers, numbered $0\sim N-1$ in order. The height of tower $i$ is $H[i]$, and its observation score is $S[i]$. Initially, $S[i]=0$.

For $0\le i\lt j\le N-1$, we say that tower $j$ can be observed from tower $i$ if and only if for any $i\le k\le j-1$, we have $H[k]\lt H[j]$. Note that when $j\le i$, tower $j$ cannot be observed from tower $i$.

When an observation operation is performed on some tower, the observation scores of all towers that can be observed from this tower will each increase by $1$.

Now there are $Q$ events, and each event is one of the following three types:

• Observe: given $I$ ($0\le I\le N-2$), perform one observation operation on tower $I$.
• Query: given $L,R$ ($0\le L\le R\le N-1$), compute $S[L]+\cdots+S[R]$.
• Shift: given $L,R,V$ ($0\le L\le R\le N-1$). For any $L\le i\le R$, set $H[i]\gets H[i]+V$.

An observe event is represented by an array $[I]$; a query event is represented by an array $[L,R]$; a shift event is represented by an array $[L,R,V]$. Note that the array sizes of these three types of events are all different, so the event type can be distinguished by the array size.

Events occur in order $0\sim Q-1$, and event $i$ is denoted by $E[i]$.

Let the total number of query events be $K$, numbered $0\sim K-1$ in the order they occur. Output the results of all query events.

Implementation Details

This is a function-style interactive problem. You do not need to, and should not, implement the main function.

You should implement the following function:

vector<long long> tower_events(vector<int> H, vector<vector<int>> E)

• $H$: an integer array of length $N$.
• $E$: an integer array of length $Q$, representing the events.
• Return an integer array $X$ of length $K$, where $X[i]$ is the result of the $i$-th query event.
• This function is called exactly once.

Input Format

The input format of the sample grader is as follows:

• Line $1$: $N$ $Q$.
• Line $2$: $H[0]$ $H[1] \dots H[N - 1]$.
• For all $0 \le i \le Q - 1$:
  • Line $3 + i$: $|E[i]|$ $E[i][0] \dots E[i][|E[i]| - 1]$.

Output Format

The sample grader outputs the answers in the following format:

• For all $0 \le i \le K - 1$:
  • Line $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

Hint

Constraints

• $5\le N\le 1\, 000\, 000$.
• $1\le Q\le 250\, 000$.
• $1\le H[i]\le 10^9$.
• For observe events, $0\le I\le N-2$.
• For query events, $0\le L\le R\le N-1$.
• For shift events, $0\le L\le R\le N-1$, $-10^9\le V\le 10^9$.
• After a shift event occurs, it is guaranteed that $H[i]\ge 1$.
• There is at least one query event.

Subtasks

Samples

Sample $1$

Consider the following call:

tower_events([1, 2, 3, 4, 5], [[0], [1, 3], [1, 2, 1], [1], [0, 4]])

• After the first event, $H = [1, 2, 3, 4, 5]$, $S = [0, 1, 1, 1, 1]$.
• The result of the second event (i.e., query event $0$) is $S[1] + S[2] + S[3] = 3$.
• After the third event, $H = [1, 3, 4, 4, 5]$, $S = [0, 1, 1, 1, 1]$.
• After the fourth event, $H = [1, 3, 4, 4, 5]$, $S = [0, 1, 2, 1, 2]$.
• The result of the last event (i.e., query event $1$) is $S[0] + \cdots + S[4] = 6$.

Therefore, this function should return $[3, 6]$.

Sample $2$

Consider the following call:

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]])

This function should return $[5, 3, 10]$.

Translated by ChatGPT 5