Big Tang Theory

If Shelly chooses a range $[a, b]$, the amount of Tang he can eat each day is the minimum value of $A_i$ in this range. Instead of finding the optimal range of the days, let’s find the optimal amount of Tang $A_i$ per day. We can find the range $[p,q]$ where $A_i$ is minimum by maintaining a monotonous stack. So, the naive approach will be: iterate from $L$ to $R$ and for each $i$, calculate the total amount of Tang he can drink if he treats $A_i$ as the Tang amount each day. The total amount will be = $A_i \times (max(L, p) - min(R, q) +1)$. The maximum of them will be the answer. Now, this approach won’t surely fit in time limit. We need to optimize it.

We can observe that, for each query $L, R$, we can classify the values $A_i$ in some types:

1. $L \leq p \leq q \leq R$. For this type, we can precalculate the total amount $A_i \times (q-p+1)$ and perform range maximum query using segment tree or similar type data structures.

2. $p<L, q\leq R$. For this type, the amount of Tang Shelly can drink is $=A_i \times (q-L+1) = A_i\times q - A_i \times (L-1)$. The only variable part here is $L-1$. It is similar to the line equation $y=m\times x + c$. So, we can apply CHT (Convex Hull Trick) to find the maximum amount in this case. Our query $x$ will be $L-1$.

3. $L\leq p, q>R$. It is similar to type $2$.

4. $p<L, q>R$. The amount of Tang Shelly can drink is $=A_i \times (R-L+1)$. As the full range is being covered, we can just find the maximum $A_i$ and then multiply it with the necessary term. Range maximum can be found by using a segment tree or similar type data structures.

The problem is how we can apply the proper operation on the proper types efficiently. To do that, we can process the queries offline.

For type $1$, we can iterate from $n$ to $1$. When we are on the $i$th index, we will process those $A_i$ that have $p=i$. We will update the value $A_i \times (q-p+1)$ on the position $q$. After that, we can process those queries that have $L=i$. We need to perform the max query on the range $[i, R]$. As the indexes $j<i$ aren’t processed yet, the already processed $p$ are $\geq L$.

For type $4$, we can iterate from $n$ to $1$ like before. When we are on the $i$th index, we will process those $A_i$ that have $q=i$. We will update the value $A_i$ on the position $p$. Before that, we need to process those queries that have $R=i$. We need to perform the max query on the range $[1, L-1]$. As the indexes $j>i$ are processed before the query, the already processed $q$ are $> R$.

For type $2$, we will iterate from $1$ to $n$. When we are on the $i$th index, we will process those $A_i$ that have $p=i$. We need to maintain such a segment tree that contains a Dynamic CHT on every node. So, when we perform an update on the position $q$, the necessary values will be inserted into the Dynamic CHT of each updatable node. The updatable nodes are the nodes of the ranges in the segment tree that include $q$. But before this update, we must process those queries that have $L=i$. We need to perform the max query on the $[i, R]$ range. Since the segment tree has Dynamic CHT on each node, we can answer it easily by performing queries on the CHT when we are on the valid nodes. As the indexes $j<i$ are processed before the query, the already processed $p$ are $< L$. We can get the values for type $3$ in a similar fashion.

After we process all the types, we can easily get our desired answer for each query.

Time complexity: $\mathcal{O}(n\times log^2(n))$