P15589 [KTSC 2026] Observation Tower / Observation Tower

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: ```cpp vector tower_events(vector H, vector 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.

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

The sample grader outputs the answers in the following format: * For all $0 \le i \le K - 1$: * Line $1 + i$: $X[i]$.

### 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 | ID | Score | Constraints | | :-: | :-: | :- | | $1$ | $17$ | $N,Q\le 150\, 000$; in all query events, $L=0,R=N-1$ | | $2$ | $ 6$ | $N,Q\le 150\, 000$; no shift events | | $3$ | $12$ | $N,Q\le 150\, 000$ | | $4$ | $19$ | in all observe events, $I=0$; in all shift events, $L=R$; shift events occur at most $30\, 000$ times | | $5$ | $21$ | in all query events, $L=R$; in all shift events, $L=R$ and $V\ge 0$ | | $6$ | $25$ | no additional constraints | ### Samples #### Sample $1$ Consider the following call: ```cpp 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: ```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]]) ``` This function should return $[5, 3, 10]$. Translated by ChatGPT 5