No.1804 Intersection of LIS
タグ : / 解いたユーザー数 57
作問者 :
NatsubiSogan
/ テスター :
nok0
penguinman
問題文
$(1,2,\dots,N)$ を並び替えた数列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。 $P$ の LIS（最長増加部分列）として考えられるものはいくつかありますが、その すべて に含まれる要素を列挙してください。
入力
$N$ $P_1$ $P_2$ $\ldots$ $P_N$
- 入力はすべて整数
- $1 \leq N \leq 3 \times 10^5$
- $P$ は $(1,2,\dots,N)$ を並び替えた数列
出力
まず、$1$ 行目に、$P$ のすべての LIS に含まれる要素の個数を出力してください。
その後、$2$ 行目に、$P$ のすべての LIS に含まれる要素を、添え字の昇順に 空白区切りで出力してください。なお、要素数が $0$ の場合は、$2$ 行目に空行を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 1 4 3 2 5
出力
2 1 5
LIS として考えられるものは、$(A_1,A_2,A_5)=(1,4,5), \ (A_1,A_3,A_5)=(1,3,5), \ (A_1,A_4,A_5)=(1,2,5)$ の $3$ つです。
これらのいずれにも含まれるのは $A_1 = 1, A_5 = 5$ なので、これらを出力します。
サンプル2
入力
3 2 3 1
出力
2 2 3
LIS は $(A_1,A_2)=(2,3)$ のみです。
サンプル3
入力
6 4 5 6 1 2 3
出力
0
すべての LIS に含まれる要素の数が $0$ である場合もあります。このような場合において、$2$ 行目は空行として出力することを忘れないで下さい。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。