AT_agc052_d [AGC052D] Equal LIS

[problemUrl]: https://atcoder.jp/contests/agc052/tasks/agc052_d $ 1 $ から $ N $ までの整数を並べ替えた列 $ P_1,\ P_2,\ \dots,\ P_N $ が与えられます。 これを、最長増加部分列の長さが等しいような $ 2 $ つの部分列に分けることは可能でしょうか。 形式的に述べると、目標は以下の条件を全て満たす $ 2 $ つの整数列 $ a,\ b $ を得ることです。 - $ a,\ b $ はともに $ P $ の部分列である。 - 各整数 $ i=1,2,\cdots,N $ は $ a,\ b $ のいずれかちょうど一方に現れる。 - ($ a $ の最長増加部分列の長さ) $ = $ ($ b $ の最長増加部分列の長さ) 目標が達成可能か判定してください。 テストケースは $ T $ 個与えられるので、それぞれを解いてください。

N/A

N/A

### 制約 - $ 1\ \le\ T\ \le\ 2\ \cdot\ 10^5 $ - $ 1\ \le\ N\ \le\ 2\ \cdot\ 10^5 $ - $ P_1,\ P_2,\ \dots,\ P_N $ は $ 1 $ から $ N $ までの整数を並べ替えた列である。 - 全テストケースにおける $ N $ の総和は $ 2\ \cdot\ 10^5 $ 以下である。 ### Sample Explanation 1 $ [1,\ 3,\ 5,\ 2,\ 4] $ を $ [1,\ 5] $ と $ [3,\ 2,\ 4] $ に分けると、両者とも最長増加部分列の長さが $ 2 $ となります。 $ [2,\ 3,\ 4,\ 5,\ 6,\ 1] $ については、最長増加部分列の長さが等しいような $ 2 $ つの部分列に分けることは不可能であることが示せます。