クエリあたり \(O(|B|)\) 時間の解法

まずは \(Q=1\) のときの答えを計算する方法を確立しましょう。\(n:=|B|\) とし、\(B=(B_1,B_2,\dots, B_n)\) が与えられたとします。

\(2\) 回以上現れる部分列が存在したとし、それを与える相異なる添字の列 \((i_1,i_2,\dots, i_k),(j_1,j_2,\dots, j_k)\) を取ります。\(k\ge 1\) が必要で、ある \(p\ (1\le p\le k)\) が存在して \(i_p\neq j_p\) となります。一般性を失わず \(i_p\lt j_p\) とします。このとき、 \((i_1,i_2,\dots, i_{p-1}, i_p,j_{p+1},j_{p+2},\dots, j_k),(i_1,i_2,\dots, i_{p-1}, j_p,j_{p+1},j_{p+2},\dots, j_k)\) もまた、同じ部分列を与える相異なる添字の列です。したがって、\(2\) 回以上現れる部分列を与える相異なる添字の列としては、添字が \(1\) 箇所だけ異なるもののみ考えればよいです。

さて、そのような相異なる添字の列を \((i_1,i_2,\dots, i_{a},l,j_{1},j_{2},\dots, j_{b}),(i_1,i_2,\dots, i_{a},r,j_{1},j_{2},\dots, j_{b})\) とします。ここで \(1\le i_1\lt i_2\lt \dots, \lt i_{a}\lt l\lt r\lt j_{1}\lt j_{2}\lt \dots \lt j_b\le n\) です。いま \(l\neq r\) かつ \(B_l=B_r\) なので、 \(B\) は重複した要素を持つ必要があります。より詳細に、次のように議論できます： \((B_s,B_{s+1},\dots, B_n)\) が重複した要素を持たないような最小の \(s\ (1\le s\le n)\) を取ります。このとき \(l\lt s\) が必要で、 \(s=1\) のときは良い列は存在しません。

\(a,b\ge 0\) と条件を満たす添字の列 \((i_1,i_2,\dots, i_{a},l,r,j_{1},j_{2},\dots, j_b)\) を先頭から順に決めていくことを考えます。先頭の添字を \(i\) とすると、\(l\lt s\) より、\(B_{i}=\max_{1\le t\lt s} B_t\) が成り立ちます。部分列は前から貪欲に取ってよいため、 \(i=\min(\mathop{\rm arg max}\limits_{1\le t\lt s}B_t)\) となります。ここで次の \(2\) つの選択肢があります。

1. \(a\ge 1\) を確定させ、 \(i_1\leftarrow i\) とする。これは \(i\lt s-1\) のとき行える。
2. \(a=0\) を確定させ、 \(l\leftarrow i, r\leftarrow \min(\lbrace t\gt i\mid B_t=B_i\rbrace)\) とする。これは \(\lbrace t\gt i\mid B_t=B_i\rbrace\neq \emptyset\) のとき行える。

いずれの場合も、 \(\lbrace t\ge s\mid B_t=B_{s-1}\rbrace\neq \emptyset\) に注意すると、それ以降を適切に選ぶことで条件を満たす添字の列を構成できます。\(2\) つの選択肢をどちらも行えるとき、どちらを選択するべきかを考えます。部分列の先頭は \(C_1=B_i\) で確定したため、次に最大化するべきは \(C_2\) です。ここで各選択肢に対する \(C_2\) は次のようになります。

1. を選んだ場合： \(B\leftarrow B(i,n]\) に対して同じ問題を解くことになるので、 \(C_2=\max_{i\lt t\lt s}B_t\) となる。
2. を選んだ場合： \(r\) より大きな添字から貪欲に最大の部分列を選ぶことになるから、 \(C_2=\max_{r\lt t\le n}B_t\) となる。

もし \(C_2\) の候補が異なる場合、大きくなる選択を取るべきです。同じ場合は、実は 1. を選択するべきです。なぜなら、2. を選択したときに選んだ \(r\) 以降の最大の部分列を \(X\) とすると、1. を代わりに選択したとして \(a'=1,i_1'=i,l'=\min(\mathop{\rm arg max}\limits_{i\lt t\lt s}B_t),r'=\min(\mathop{\rm arg max}\limits_{r\lt t\le n}B_t)\) とすれば同じように \(X\) を取ることができるからです。ここで、 \(l'\lt r'\) となるのは次のようにして分かります：まず \(s\le r'\) のときは \(l'\lt s\) から明らかです。 \(r'\lt s\) のときは、 \(r,r'\) の定義から \(i\lt r\lt r'\lt s\) で、 \(B_i\) の \([1,s)\) での最大性と \(B_i=B_r\) をあわせると \(\max_{i\lt t\lt s}B_t=B_r\) となります。これに \(l'\) の定義を照らし合わせると \(l'\le r\) となり、結局 \(l'\le r\lt r'\) となって結論が得られます。

以上で、添字の列を先頭から決めていく最適な戦略が得られました。実装は

• \(s\)
• \(\mathrm{tolim}_i=\min(\argmax_{i\lt t\lt s} B_t)\)
• \(\mathrm{toend}_i=\min(\argmax_{i\lt t\le n} B_t)\)
• \(\mathrm{nxt}_i=\min(\lbrace t\gt i\mid B_t=B_i\rbrace)\)

を前計算し、\(2\) つの選択肢が発生するたびに次の値（ \(C_2\) ）の大小比較を行って選択を決定します。1. を選んだ場合は同様の手順で続行し、2. を選んだ場合は \(r\) より大きい添字から最大の部分列を貪欲に取ればよいです。これらは \(O(|B|)\) 時間で行うことができます。

疑似コードによる実装は次の通りです。入力や前計算、およびローリングハッシュの取得については省略しています。

# B[1],...,B[m] は処理した
m = 0
ans = []
while true :
    i = tolim[m]
    ans.append(B[i])
    if i == s-1 :
        m = nxt[i]
        break
    if nxt[i] != infty && B[tolim[i]] < B[toend[nxt[i]]] :
        m = nxt[i]
        break
    m = i
while m < n :
    i = toend[m]
    ans.append(B[i])
    m = i

高速化

\((L_i,R_i)\) から定められる \(B=(A_{L_i},A_{L_i+1},\dots, A_{R_i})\) に対して上述の \(O(|B|)\) 時間の解法を適用することを考えると、解法中に登場した \(s,\mathrm{tolim},\mathrm{toend}\) は \(R_i\) に強く依存し、逆に \(L_i\) にはほとんど依存しないことが分かります。そこで、クエリを先読みして、\(R_i\) の昇順に処理することにします。

\(B=(A_1,A_2,\dots, A_R)\) に対する \(s,\mathrm{tolim},\mathrm{toend},\mathrm{nxt}\) が計算されているものとします。 \(L\lt s\) であるとして、上述の疑似コードをクエリ \((L,R)\) に対応するように書き換えると、次のようになります。

# A[L],...,A[m] は処理した
m = L-1
ans = []
while true :
    i = tolim[m]
    ans.append(A[i])
    if i == s-1 :
        m = nxt[i]
        break
    if nxt[i] != infty && A[tolim[i]] < A[toend[nxt[i]]] :
        m = nxt[i]
        break
    m = i
while m < R :
    i = toend[m]
    ans.append(A[i])
    m = i

この疑似コード中で break されるときの \(i\) を高速に取得できたとし、その \(i\) を \(i_{L,R}\) と書きます。このとき、辞書順で最大の良い列は次のような構造になっています。

• \(\mathrm{tolim}\) に現れる添字 \(i\) のうち \(L\le i\lt i_{L,R}\) を満たすものを昇順に並べて \((i_1,i_2,\dots, i_a)\) とする
• \(\mathrm{toend}\) に現れる添字 \(j\) のうち \(\mathrm{nxt}_{i_{L,R}}\lt j\le R\) を満たすものを昇順に並べて \((j_1,j_2,\dots, j_b)\) とする
• 辞書順で最大の良い列は \((A_{i_1},A_{i_2},\dots, A_{i_a}),(A_{i_{L,R}}),(A_{j_1},A_{j_2},\dots, A_{j_b})\) をこの順に結合したものに一致する

したがって、\(\mathrm{tolim}\) や \(\mathrm{toend}\) に現れる添字 \(i\) の位置に \((A_i)\) のローリングハッシュを乗せたセグメント木をそれぞれ用意することで、各 \(L\) に対する答えの取得を \(O(\log N)\) 時間で行うことができます。

さて、疑似コード中の if 文が \(L\) に依存していないことから、\(i_{L,R}\) は次のように特徴付けられます。\(R\) のみ固定して \(L\lt s\) を任意に取ったときに \(i_{L,R}\) の候補となるのは、疑似コード中のいずれかの if 文の条件にあてはまるような \(\mathrm{tolim}\) に現れる添字に限ります。そのような添字の集合を \(I_R\) とおくと、\(i_{L,R}\) は \(I_R\) の要素であって \(L\) 以上のもののうち最小のものになります。\(I_R\) を std::set などの平衡二分木で管理すれば、\(i_{L,R}\) の取得は \(O(\log N)\) 時間で行うことができます。

残る課題は \(R\) を \(1\) だけ増やしたときの \(s,\mathrm{tolim},\mathrm{toend},\mathrm{nxt}\) の更新や、それに伴うローリングハッシュを乗せたセグメント木の更新、および \(I_R\) の更新です。

まず、\(s\) は \(R\) の増加に関して単調に増加します。\(\mathrm{tolim}\) や \(\mathrm{toend}\) はそれぞれ \(s,R\) の増加に伴って変化しますが、それに現れる添字の集合はスタックを用いて管理できます。\(\mathrm{nxt}\) の更新は \(R\) が \(1\) だけ増加したときに高々 \(1\) 箇所変化します。ここまでで、\(I_R\) の更新を除けば、必要な更新は全体で \(O(N\log N)\) 時間で行うことができます。

\(\mathrm{tolim}\) に現れる添字の集合を \(S\) とすると \(I_R\subseteq S\) です。\(I_R\) は次のようにして更新することになります。ただし、空集合に対する \(\min,\max\) を適切に定め、\(A\) に番兵を追加することで、break のための if 文は A[tolim[i]] < A[toend[nxt[i]]] のみに集約します。見やすさのため、\(A_*\) を \(A[*]\) とも表記します。

• \(\mathrm{tolim}\) のスタックから取り出された \(i\) は二度と \(I_R\) の要素にならない。
• \(i\in S\) について \(d_i=A[\mathrm{toend}_{\mathrm{nxt}_i}]-A[\mathrm{tolim}_i]\) を考えると、\(d_i\gt 0\) であることが \(I_R\) の要素である条件となる。
• \(\mathrm{nxt}\) の更新は、高々 \(1\) 個の \(i\in S\setminus I_R\) （ \(\mathrm{nxt}_i=R\) ）について \(d_i\) を増加させて新たに \(I_R\) の要素になる。
• \(\mathrm{tolim}\) の更新は、高々 \(1\) 個の \(i\in S\) （スタックの top）について \(d_i\) を減少させて \(I_R\) の要素ではなくなる。
• \(\mathrm{toend}\) の更新は、\(\mathrm{nxt}_i\) がある範囲に入るような \(i\in S\setminus I_R\) について \(d_i\) を増加させ、高々 \(1\) つを除いて新たに \(I_R\) の要素になる。
  • 範囲内の \(\mathrm{nxt}_i\) が \(\mathrm{toend}\) のスタックの top ではないとき、\(A[\mathrm{nxt}_i]\lt A[\mathrm{toend}_{\mathrm{nxt}_i}]\) となる。さらに \(i\in S\) より \(A[i]\ge A[\mathrm{tolim}_i]\) であるから、\(d_i=A[\mathrm{toend}_{\mathrm{nxt}_i}]-A[\mathrm{tolim}_i]\gt A[\mathrm{nxt}_i]-A[i]=0\) より、\(I_R\) の要素になる。

\(I_R\) の要素であったものがそうでなくなる回数が全体で \(O(N)\) 回と評価できるため、最後の項目は範囲内の \(S\setminus I_R\) の要素について愚直に調べても計算量は悪化しません。たとえば、\(S\setminus I_R\) を \(\mathrm{nxt}_i\) をキーにして std::set などの平衡二分木で管理し、特定の範囲について愚直に走査すれば良いです。

これらを更新順序に十分注意して丁寧に実装することで、この問題に正答できます。この解法の時間計算量は \(O((N+Q)\log N)\) です。