First, consider the case \(Q=1\). Roughly speaking, we need to solve the following:

We have a permutation \(P\) of \((1, 2, \dots, N)\). On a 2D coordinate plane, there is a point \((i, P_i)\) for each \(i\).
Each point is colored red or blue, with \(L\) blue points in total.
From each blue point, you can take a path that starts from it and successively visits a red point that is to the left and below of the current point. (Call this path a chain.)
Maximize the total number of points in these \(L\) chains when the chains must not share a point.

Though one can solve this by a flow-based approach in \(\mathrm{O}(LN \,\mathrm{polylog}(N))\) time, we try to solve it in another way.

Let us consider conditions under which swapping \(P_i\) and \(P_{i+1}\) (and simultaneously swapping their point colors) does not affect the answer. We obtain five such conditions:

• Points \(i, i+1, i+2\) are all red, and \(\min(P_i, P_{i+1}) < P_{i+2} < \max(P_i, P_{i+1})\).
  
• Points \(i-1, i, i+1\) are all red, and \(\min(P_i, P_{i+1}) < P_{i-1} < \max(P_i, P_{i+1})\).
  
• Point \(i\) is red, point \(i+1\) is blue, and \(P_i > P_{i+1}\).
  
• Points \(i, i+1\) are red, point \(i+2\) is blue, and \(P_{i+1} < P_{i+2} < P_i\).
  
• Points \(i-1, i\) are red, point \(i+1\) is blue, and \(P_i < P_{i-1} < P_{i+1}\).

Using these swaps extensively, we can transform \(P\) and the color assignment into the following normal form. (\(+\) denotes concatenation of sequences.)

\[ \begin{aligned} P &= (a_{1,1}, a_{1,2}, \dots, a_{1,n_1}) \\ & \quad\;\; \vdots \\ &+ (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) \\ &+ (b_{1,1}, b_{1,2}, \dots, b_{1,m_1}) \\ & \quad\;\; \vdots \\ &+ (b_{l,1}, b_{l,2}, \dots, b_{l,m_l}), \end{aligned} \]

where:

• The points corresponding to \(a_{i,1}, \dots, a_{i,n_i-1}\) are red, and the point corresponding to \(a_{i,n_i}\) is blue.
• \(a_{i,1} < a_{i,2} < \dots < a_{i,n_i}\)
• \(b_{i,j}\) are all red.
• \(b_{i,j} < b_{i,j+1}, b_{i-1,j} > b_{i,j}\)

Simply speaking, each row of \(a\) is a chain starting from a blue point, and \(b\) is the tableaux obtained by Robinson–Schensted (RS) correspondence arranged from bottom to top. Also, the maximum value of the sum of chain lengths here is clearly \(\sum_{i=1}^k n_i\).

We consider how to compute the normal form of \(P\). Let us start with an empty sequence and add one element at a time to the end, updating the normal form each time.

If the element to be added is red, it can be seen that it is possible to use swaps to update \(b\) in a manner analogous to the RS correspondence, so we do this.

Consider the case where the element to be added is blue. Let \(x\) be this element. We use the third kind of swap to move \(x\) as far left as possible, making the last portion of \(P\) look like \((b_{l,1}, b_{l,2}, \dots, b_{l,k}, x, b_{l,k+1}, \dots, b_{l,m_l})\). Then, in an optimal solution, the chain starting from \(x\) has length \(k\). From here, we will keep moving reds that are to the left of \((b_{l,1}, b_{l,2}, \dots,b_{l,k}, x)\) to the right, and swapping values with \(b_{l,\ast}\) one by one if needed. This procedure can be described as simple operations using lower_bound, similarly to the case with RS correspondence. (It can be proved that there will be no problem during these operations from the tableau-like structure of \(b\).)

In this way, we can transform \(P\) into its normal form. Here, observe that we only need to maintain a number of rows in \(b\) equal to the number of blues to the right \((\leq L)\). This fact allows us to reduce the complexity of updating \(P\) when adding a red point. Now, each insertion of a red point takes \(\mathrm{O}(L \log N)\) time, and each insertion of a blue point takes \(\mathrm{O}(N \log N)\) time, for a total of \(\mathrm{O}(L N \log N)\) time to solve the subproblem.

The same method can be used to solve the problem with \(Q\) \((\gt 1)\) queries. Let \(L = K + \max(X_i)\). We precompute the normal form for the first \(N+K\) elements, using the fact that we only need the rightmost \(L\) rows of \(b\). For each query, we can find the count by a lower_bound operation with \(Y_i\) for the rightmost \(X_i\) rows of \(b\). This solves the problem in \(\mathrm{O}((N + Q) L \log N)\) time, which is sufficiently fast.