AT_abc237_g [ABC237G] Range Sort Query

[problemUrl]: https://atcoder.jp/contests/abc237/tasks/abc237_g $ 1,2,\ldots,N $ を並び替えた長さ $ N $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ と整数 $ X $ が与えられます。 また、$ Q $ 個のクエリが与えられます。 $ i $ 番目のクエリは $ 3 $ つの数の組 $ (C_i,L_i,R_i) $ で表されます。各クエリでは順列 $ P $ に対して次の操作を行います。 - $ C_i=1 $ のとき : $ P_{L_i},P_{L_i+1},\ldots,P_{R_i} $ を昇順に並び替える。 - $ C_i=2 $ のとき : $ P_{L_i},P_{L_i+1},\ldots,P_{R_i} $ を降順に並び替える。 クエリを $ 1 $ 番目から順に最後まで処理したとき、最終的な順列において $ P_i=X $ となる $ i $ を求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ X\ \leq\ N $ - $ (P_1,P_2,\ldots,P_N) $ は $ (1,2,\ldots,N) $ の並び替えである。 - $ 1\ \leq\ C_i\ \leq\ 2 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - 入力は全て整数である。 ### Sample Explanation 1 最初、順列は $ P=[1,4,5,2,3] $ です。 これはクエリによって次のように変化します。 - $ 1 $ つめのクエリでは $ 3 $ 番目から $ 5 $ 番目の要素を昇順にソートします。順列は $ P=[1,4,2,3,5] $ となります。 - $ 2 $ つめのクエリでは $ 1 $ 番目から $ 3 $ 番目の要素を降順にソートします。順列は $ P=[4,2,1,3,5] $ となります。 最終的な順列において $ P_3=1 $ であるので、$ 3 $ を出力します。 ### Sample Explanation 2 最終的な順列は $ P=[1,2,6,5,7,4,3] $ となります。