Maximum Stability of Interleaved Sequences

Given two sequences of positive integers, \(a = [a_0, a_1, \ldots, a_{n-1}]\) and \(b = [b_0, b_1, \ldots, b_{m-1}]\), we say that a sequence \(h = [h_0, h_1, \ldots, h_{k-1}]\) is good if it can be partitioned into two subsequences \(p\) and \(q\) (not necessarily contiguous) such that

\(p = a\) and \(q = b\).

The weight of a sequence \(h\) is defined as

[ W(h) = \max_{0 \le l \le r < k} \Bigl((r-l+1)\cdot \min_{l \le i \le r} {h_i}\Bigr). ]

Define \(f(a, b)\) to be the maximum possible weight among all good sequences formed by interleaving \(a\) and \(b\) (while preserving the order of elements in each sequence).

You are given \(q\) queries. In the \(i\)th query, you are given indices \(L_i\) and \(R_i\) and you must compute \(f(a, b')\) where \(b'\) is the subarray \(b_{L_i}, b_{L_i+1}, \ldots, b_{R_i}\).

Observation and Hint

It can be shown that for any candidate value \(x\) (which must be one of the elements in \(a\) or \(b'\)), if we let

[ \text{cnt}a(x)=#{ i: a_i \ge x }, \quad \text{and} \quad \text{cnt}{b'}(x)=#{ i: b'_i \ge x }, ]

then by an appropriate interleaving, one can achieve a contiguous block of \(\text{cnt}_a(x)+\text{cnt}_{b'}(x)\) elements, all of which are at least \(x\), giving a weight of at least

[ (\text{cnt}a(x)+\text{cnt}{b'}(x)) \cdot x. ]

Thus, the answer is given by

[ \max_{x\in (a \cup b')} {(\text{cnt}a(x)+\text{cnt}{b'}(x)) \cdot x}. ]

</p>

inputFormat

Function Signature: vector max_stability(vector a, vector b, vector L, vector R)

The function receives:

• a: A sequence of \(n\) positive integers.
• b: A sequence of \(m\) positive integers.
• L and R: Two sequences of \(q\) non-negative integers where each pair \((L_i, R_i)\) describes a query.

For each query, consider the subarray \(b' = [b_{L_i}, b_{L_i+1}, ..., b_{R_i}]\) and compute \(f(a, b')\) as described above. The function should return a vector of \(q\) answers.

outputFormat

The function should return a vector of \(q\) non-negative integers. The \(i\)th integer is the answer to the \(i\)th query, i.e. the maximum weight obtainable for the interleaving of a and the subarray of b defined by indices [L_i, R_i].

sample

n = 2, m = 3
 a = [3, 1]
 b = [2, 3, 1]
 q = 2
 L = [0, 1]
 R = [1, 2]

Explanation:
For query 1, b' = [2, 3]. The candidates are {1,2,3}:
Candidate 1: count_a = 2, count_b = 2, product = 4
Candidate 2: count_a = 1 (only 3 qualifies), count_b = 2, product = 6
Candidate 3: count_a = 1, count_b = 1, product = 3
So answer is 6.
For query 2, b' = [3, 1].
Candidate 1: count_a = 2, count_b = 2, product = 4
Candidate 3: count_a = 1, count_b = 1, product = 2
Answer: 4

6
4

</p>