この問題は、同じタイミングで出題された STPC2025(Div. 1)-E Max Twice Subsequences の簡単版です。

ここでは \(O(N+\sum_{i=1}^{Q}(R_i-L_i+1))\) 時間の解法のみを紹介しますが、この制約がなくても \(O((N+Q)\log N)\) 時間で解くことができます。

クエリ毎に独立に問題に答えます。\(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

実装の際は \(1\le B_i\le n\) とは限らないことに注意してください。全体で長さ \(N\) の配列を使いまわすなどすれば、 \(O(N+\sum_{i=1}^{Q}(R_i-L_i+1))\) 時間で動作する解法が得られます。