If \(X_i\) are all equal

Let \(X\) be the equal value. For simplicity, suppose that every term is covered by some segment \([L_i, R_i]\). Then every value should not exceed \(X\), and the condition for the segment \([L_i, R_i]\) can be rephrased as “at least one of \(A_{L_i}, \dots, A_{R_i}\) equals \(X\).”

Then, the number of \(A\) satisfying the conditions can be found by the following Dynamic Programming (DP).

\(\text{dp}_{i, j} :=\) The number of ways to determine the first \(i\) terms of the sequence so that all the conditions such that \(R_k \leq i\) are satisfied and the last occurrence of \(X\) is at the \(j\)-th term.

This can be written by an in-place DP as follows:

• Find the value of \(\text{dp}_j\) using \(\text{dp}_1, \dots, \text{dp}_{j-1}\).
• Let \(l\) be the minimum \(L_k\) such that \(R_k = j\). Replace all \(\text{dp}_1, \dots, \text{dp}_{l-1}\) with \(0\).

This can be computed in a total of \(O(N + Q)\) time using cumulative sums or sliding window technique.

Solution for the original problem.

Prepare a segment \(B = (B_1, \dots, B_N)\) of length \(N\) to store the upper bound of \(A_i\). Initialize each term of \(B\) with \(M\).

For each \(j = 1, \dots, Q\), do the following:

For \(i = L_j, \dots, R_j\), replace \(B_i\) with \(\min(B_i, X_j)\).

This can be computed in a total of \(O((N + Q) \log N)\) time.

Now, for the condition \(\max(A_{L_i}, \dots, A_{R_i}) = X_i\), we don’t have to consider the terms such that \(B_{k} \lt X_i\). Also, obviously, the terms such that \(B_k \gt X_i\) are not contained in \([L_i, R_i]\). So, for a fixed \(X\), consider determining \(A_k\) only for all terms such that \(B_k = X\) subject only to the conditions such that \(X_i = X\); actually this is equivalent to the problem we described in the last section. Find the answer for this subproblem for each \(X\), and the answer for the original problem is obtained as their product.

By performing coordinate compression for \(B_k = X\) and applying the solution for the last problem, the problem can be solved in a total of \(O((N + Q) \log N)\) time.

Sample code (C++)