Problem Description

Given sequences $a_{0\sim n-1}$ and $b_{0\sim m-1}$, define:

$$f(a,b)=\max_{0\le l\le r\le |a|-1}\;\max_{0\le L\le R\le |b|-1}(r-l+1+R-L+1)\times \min\{a[l,r],b[L,R]\}$$

There are $q$ queries $(l_j,r_j)$, asking for the value of $f(a,b[l_j,r_j])$.

Constraints

• $1\le n,q\le 1.5\times 10^5$
• $1\le q\le 5\times 10^5$
• $1\le a_i,b_i\le 10^9$
• $0\le l_j\le r_j\le m-1$
• Time limit: $10\text{s}$, Memory limit: $1024\text{MB}$

Solution

Assume $n,m,q$ are of the same order.

Clearly, the chosen intervals are maximal. First preprocess them using a monotonic stack.

For sequence $a$, it's simple. Precompute $\text{len}_i$ as the length of the maximal interval containing $a_i$, and $\text{maxlen}(v)$ as the maximum length of an interval whose minimum value is $\ge v$. The answer without selecting from $b$ is $\max_{1\le i\le n} \{a_i\times \text{len}_i\}$, which can be computed directly.

If we select from $b$, let the maximal interval containing $b_i$ be $[\text{pl}_i,\text{pr}_i]$. The answer is:

$$\max_{1\le i\le m,\;v\le b_i} \left\{v\times\left(|[\text{pl}_i,\text{pr}_i]\cap[l_j,r_j]| + \text{maxlen}(v)\right)\right\}$$

We classify based on the positional relationship between $[\text{pl}_i,\text{pr}_i]$ and $[l_j,r_j]$.

Case 0: $l_j\le \text{pl}_i\le \text{pr}_i\le r_j$

Take the entire $[\text{pl}_i,\text{pr}_i]$. Precompute the answer for each interval.

We need to compute $\max_{v \le b_i} \{v\times(\text{maxlen}(v)+\text{pr}_i-\text{pl}_i+1)\}$. Treat this as a linear function in $(\text{pr}_i-\text{pl}_i+1)$. Process in increasing order of $b_i$, first inserting all functions with $v\le b_i$, then querying the maximum at $x=\text{len}_i$. Use a Li Chao tree for maintenance.

After computing the answer for each $[\text{pl}_i,\text{pr}_i]$, answer queries with a single sweep line. This part is $O(n\log n)$.

Case 1: $\text{pl}_i\le l_j\le r_j\le \text{pr}_i$

Here we take $[l_j,r_j]$. We need $\max_{v \le b_i} \{v\times(\text{maxlen}(v)+r_j-l_j+1)\}$. Process each query directly using the same method as Case 0. Complexity is also $O(n\log n)$.

Case 2: $\text{pl}_i\le l_j\le\text{pr}_i \le r_j$

Here we take $[l_j,\text{pr}_i]$, a prefix. We need $\max_{v \le b_i} \{v\times(\text{maxlen}(v)+\text{pr}_i-l_j+1)\}$. Use a sweep line on $r$.

For each $v$, maintain the value $v\times (\text{maxlen}(v)+c_v)$, where $c_v$ is the maximum length of a suffix of $b[1,r]$ whose minimum value is $\ge v$. As $r$ moves, increment $c$ globally by $1$. Then for all $v > b_r$, set $c_v$ to $0$.For a query, find the maximum value of $v$ such that $c_v \le r_j-l_j+1$.

Use sqrt-decompsition with convex hulls. Each block maintains a $\text{tag}$. Since $c_v$ is monotonically non-increasing, each query looks at a suffix. Due to monotonicity, the optimal tangent point on the convex hull moves forward monotonically; maintain pointers accordingly. Reset pointers when clearing. Process whole blocks as above; for partial blocks, brute force then rebuild. Amortized complexity is $O(n\sqrt n)$.

Case 3: $l_j\le \text{pl}_i\le r_j\le \text{pr}_i$

Here we take $[\text{pl}_i, r_j]$, a suffix. We need $\max_{v \le b_i} \{v\times(\text{maxlen}(v)+r_j-\text{pl}_i+1)\}$. Similar to Case 2, but sweep on $l$. Complexity is $O(n\sqrt n)$.