Subtask 1

If a meeting place is given, you can calculate the cost of a meeting in $\mathcal{O}(N)$. Thus, by testing every possible meeting place, the cost of a meeting can be calculated in $\mathcal{O}(N^2)$ time.

The total time complexity is $\mathcal{O}(N^{2}Q)$.

Subtask 2

By iterating through the mountains with maintaining an upper envelope, you can get costs for all meeting places in $\mathcal{O}(N)$ time.

The total time complexity is $\mathcal{O}(NQ)$.

Subtask 3

Find the longest contiguous subsequence consisting only of $1$ by SegmentTree. The total time complexity is $\mathcal{O}(N+Q\log N)$.

Subtask 4

For each meeting, divide the range at the highest mountains and recursively solve the problem.

If you pre-calculate the answer to some ranges, such as maximal ranges in which heights of all mountains are at most some constant, and you prepare a proper data structure for Range Minimum Queries, you can get the minimum cost of a meeting in $\mathcal{O}(max\{H_i\}\log N)$ time.

Pre-calculation can be done in $\mathcal{O}(max\{H_i\}N)$ time.

The total time complexity is $\mathcal{O}(max\{H_i\}(N+Q\log N))$.

Subtask 5

For convenience, let's assume that all values of $H$ are distinct (this does not matter much). For each meeting, we can assume that the index of the optimal meeting place is greater than or equal to $\arg \underset{L\le i\le R}{max}(H_i)$, because by reversing the array $H$ and solving the same problem we can get a real answer.

We denote the problem of calculating the minimum cost of a meeting with the range $[L,R]$ as query $[L,R]$.

• Let $\mathrm{Cost}(L,R)$ be the answer to the query $[L,R]$.
• Let $\mathrm{RangeL}(v)$ be the smallest $x$ such that $\arg \underset{x\le i\le v}{max}(H_i)=v$.
• Similarly, let $\mathrm{RangeR}(v)$ be the largest $x$ such that $\arg \underset{v\le i\le x}{max}(H_i)=v$.
• Also, let $S(v)$ be the array of length

$${\displaystyle \mathrm{RangeR}(v)-\mathrm{RangeL}(v)+1}$$

such that the $i^{\text{th}}$ ($0\le i\le \mathrm{RangeR}(v)-\mathrm{RangeL}(v)$) value of $S(v)$ is

$${\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v),\mathrm{RangeL}(v)+i)}$$

We are going to compute $S(v)$ for all $v$, and then it is easy to get answers to all queries. The order of indices in which we compute $S(v)$ is very important. Here, we use depth-first-search post-order of the cartesian tree of $H$.

We define the cartesian tree of $H$ as the rooted tree such that the lowest-common-ancestor of nodes $u$ and $v$ is the node $\arg \underset{u\le i\le v}{max}(H_i)$.

The cartesian tree can be obtained in linear time by an iteration with a stack data structure. It can be easily seen that every node of the cartesian tree has at most two children, one to the left and another to the right. Let $lc(v)$ be the left child of the node $v$ and $rc(v)$ be the right child of the node $v$ (here we assume that the node $v$ has two children).

Now the remaining task is to somehow merge $S(lc(v))$ and $S(rc(v))$ into $S(v)$. Clearly, first some elements of $S(v)$ is exactly $S(lc(v))$.

All we need is to compute $\mathrm{Cost}(\mathrm{RangeL}(v),p)$, for all $p$ ($v\le p$).

Since $H_v$ is the maximum value in the range $[\mathrm{RangeL}(v),\mathrm{RangeR}(v)]$, you can see

$${\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v),p)=min\{\mathrm{Cost}(\mathrm{RangeL}(v),v)+(p-v)\times H_v,(v-\mathrm{RangeL}(v)+1)\times H_v+\mathrm{Cost}(v+1,p)\}}$$

and

$${\displaystyle \begin{array}{rl}& \phantom{\le }(\mathrm{Cost}(\mathrm{RangeL}(v),v)+(p-v)\times H_v)-((v-\mathrm{RangeL}(v)+1)\times H_v+\mathrm{Cost}(v+1,p))\\ & \le (\mathrm{Cost}(\mathrm{RangeL}(v),v)+(p+1-v)\times H_v)-((v-\mathrm{RangeL}(v)+1)\times H_v+\mathrm{Cost}(v+1,p+1))\end{array}}$$

where $p+1\le \mathrm{RangeR}(v)$.

The inequality follows from the observation that

$${\displaystyle \mathrm{Cost}(v+1,p+1)-\mathrm{Cost}(v+1,p)\le \underset{v+1\le i\le p+1}{max}(H_i)\le H_v}$$

It indicates that there exists a certain index $z$ such that

$${\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v),p)=\mathrm{Cost}(\mathrm{RangeL}(v),v)+(p-v)\times H_v}$$

for all $p\le z$, and

$${\displaystyle \mathrm{Cost}(\mathrm{RangeL}(v),p)=(v-\mathrm{RangeL}(v)+1)\times H_v+\mathrm{Cost}(v+1,p)}$$

for all $z<p$.

Therefore, you can get $S(v)$ in the following way:

• Let $T$ be the array obtained by adding a certain value to all elements of $S(rc(v))$.
• Update first some elements of $T$ with a certain linear function.
• Concatenate $S(lc(v))$, $\mathrm{Cost}(\mathrm{RangeL}(v),v)$, and $T$.

To carry out these operations fast, we use a compressed representation for $S(v)$. $S(v)$ is represented by the list of ranges. Each range has a certain linear function such that the values of $S(v)$ in the range can be calculated by the linear function.

Adding a certain value can be done by lazy propagation.

To update first some elements, we simply iterate through $T$ from the beginning. The ranges before the break point are replaced by one range, so the total number of iterations is $\mathcal{O}(N)$.

Concatenating two arrays can be done as follows:

• We maintain end points of ranges in a global set and store the information of ranges in a global array. Then, we do not have to do anything for ranges.
• Concatenating lazy propagation information for adding can be done by Weighted-union heuristic:
  • Let $W(s)$ be the value which should be added to elements of the array $s$.
  • When we concatenate two arrays $s$ and $t$, we pick the smaller one and arrange the elements of it so that $W(s)=W(t)$.
  • By Weighted-union heuristic, this can be done in $\mathcal{O}(N\log N)$ time in total.

Getting the answer to a query requires one lower bound operation of the set. Thus in $\mathcal{O}(Q\log N)$ time we can get answers to all queries.

The total time complexity is $\mathcal{O}((N+Q)\log N)$.