[ABC237G] Range Sort Query

## 题面 现有一个 $1 \sim N$ 的排列 $P = (P_1,P_2,\ldots,P_N)$ 和一个正整数 $X$。 接下来会进行 $Q$ 次操作，每次操作给出三个正整数 $(C_i,L_i,R_i)$： - 若 $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}$ 按降序排序。 请输出最后数 $X$ 所在的位置，即输出满足 $P_i = X$ 的正整数 $i$。 ## 输入 输入第一行，共三个正整数 $N,Q,X$。 接下来 $N$ 行，每行三个正整数 $C_i,L_i,R_i$，表示一次操作。 ## 输出 一行一个正整数表示答案。 ## 数据范围&提示 $1 \le N, Q \le 2 \times 10^5,1 \le X \le N\\[1.5ex] 1 \le C_i \le 2,1 \le L_i \le R_i \le N$。 保证输入全部是正整数。

[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 $ $ Q $ $ X $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ C_1 $ $ L_1 $ $ R_1 $ $ C_2 $ $ L_2 $ $ R_2 $ $ \vdots $ $ C_Q $ $ L_Q $ $ R_Q $

答えを出力せよ。

5 2 1
1 4 5 2 3
1 3 5
2 1 3

3

7 3 3
7 5 3 1 2 4 6
1 1 7
2 3 6
2 5 7

7

### 制約 - $ 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] $ となります。