まずは \(Q = 1\) の場合を考えます。およそ次の問題が解ければよいです。

長さ \(N\) の順列 \(P\) がある。2 次元座標上の \((i, P_i)\) に点がある。
各点は赤い点か青い点である。青い点は \(L\) 点あるとする。
青い点からスタートして、今いる点よりも左下にある赤い点を通っていくパス (これを chain と呼ぶ) を自由に取ることができる。
chain 同士は点を共有しない時、\(L\) 本の chain に含まれる点の個数を最大化せよ。

この問題はフローで \(\mathrm{O}(LN \mathrm{polylog}(N))\) で解けますが、フローを流さずに問題を解くことを考えます。

\(P_i\) と \(P_{i+1}\) を swap して(対応する点の色も同時に swap する) 答えが変わらない条件を考えます。すると次の \(5\) 個の条件が得られます。

• 点 \(i, i+1, i+2\) が赤い点で、\(\min(P_i, P_{i+1}) \lt P_{i+2} \lt \max(P_i, P_{i+1})\)
• 点 \(i-1, i, i+1\) が赤い点で、\(\min(P_i, P_{i+1}) \lt P_{i-1} \lt \max(P_i, P_{i+1})\)
• 点 \(i\) が赤い点、点 \(i+1\) が青い点で、\(P_i \gt P_{i+1}\)
• 点 \(i,i+1\) が赤い点、点 \(i+2\) が青い点で、\(P_{i+1} \lt P_{i+2} \lt P_i\)
• 点 \(i-1,i\) が赤い点、点 \(i+1\) が青い点で、\(P_i \lt P_{i-1} \lt P_{i+1}\)

これらの swap を駆使すると、\(P\) および対応する点の色の組を次の標準形に変形することが出来ます。(ここで \(+\) は列の結合を意味する)

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

ただし、

• \(a_{i,1}, \dots, a_{i,n_i-1}\) に対応する点は赤、\(a_{i,n_i}\) に対応する点は青
• \(a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,n_i}\)
• \(b_{i,j}\) は全て赤
• \(b_{i,j} \lt b_{i,j+1}, b_{i-1,j} \gt b_{i,j}\)

簡単に言うと、\(a\) の各行は青い点を始点とする chain で、\(b\) はロビンソン・シェンステッド対応 (RS 対応)で得られるタブローを下の行から順に並べたものになっています。また、この時の chain の長さの和の最大値は明らかに \(\sum_{i=1}^k n_i\) です。

\(P\) の標準形を得る方法を考えます。空の列からスタートして末尾に要素を 1 個ずつ追加していき、そのつど標準形を更新するという方法で標準形を得ることにします。
追加する要素が赤い色である場合は、swap を駆使すれば RS 対応と同様の手順で \(b\) を更新できることが分かるので RS 対応の要領で更新すればよいです。
追加する要素が青色である場合を考えます。追加する要素を \(x\) とします。3 番目の swap を使って \(x\) を可能な限り左に持って行って \(P\) の末尾が \((b_{l,1}, b_{l,2}, \dots,b_{l,k}, x, b_{l,k+1}, \ldots, b_{l,m_l})\) という形になったとします。この時、最適解において \(x\) を始点とする chain の長さは \(k\) なので、ここからは \((b_{l,1}, b_{l,2}, \dots,b_{l,k}, x)\) の左にある赤を右に移し、必要に応じて \(b_{l,\ast}\) と値を入れ替える操作を \(1\) 個ずつ行うことになります。これは RS 対応の時と同様 lower_bound を用いた簡単な操作で記述できます。(この操作中に問題が起こらないことは \(b\) がタブロー状の形をしていることから示せます。)

以上の方法で \(P\) の標準形を得ることが出来ました。ここで、答えを求めるためには \(b\) の部分は右にある青の個数分の行数 \((\leq L)\) しか保持しなくてよい点に注目すると、赤い点を追加する時の \(P\) の更新の計算量を抑えることが出来ます。よって、赤い点を追加する時の計算量は \(\mathrm{O}(L \log N)\)、青い点を追加する時の計算量は \(\mathrm{O}(N \log N)\) となるため、全体で \(\mathrm{O}(L N \log N)\) で部分問題を解くことが出来ます。

クエリが \(Q\) \((\gt 1)\) 個ある場合も同様の方法で解けています。\(L = K + \max(X_i)\) とします。\(b\) の右 \(L\) 行だけが必要であるのを利用しつつ先頭 \(N + K\) 個の標準形をあらかじめ計算しておいて、クエリに答える時は \(b\) の右から \(X_i\) 行を \(Y_i\) で lower_bound する形で個数を数えられます。これで \(\mathrm{O}((N + Q) L \log N)\) で問題を解けていて、これは十分高速です。