/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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 を求めてください。
制約
- 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
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
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
出力
答えを出力せよ。
入力例 1
5 2 1 1 4 5 2 3 1 3 5 2 1 3
出力例 1
3
最初、順列は 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 を出力します。
入力例 2
7 3 3 7 5 3 1 2 4 6 1 1 7 2 3 6 2 5 7
出力例 2
7
最終的な順列は P=[1,2,6,5,7,4,3] となります。
Score : 600 points
Problem Statement
Given is a permutation P=(P_1,P_2,\ldots,P_N) of 1,2,\ldots,N, and an integer X.
Additionally, Q queries are given. The i-th query is represented as a triple of numbers (C_i,L_i,R_i). Each query does the following operation on the permutation P.
- If C_i=1: sort P_{L_i},P_{L_i+1},\ldots,P_{R_i} in ascending order.
- If C_i=2: sort P_{L_i},P_{L_i+1},\ldots,P_{R_i} in descending order.
In the final permutation P after executing all queries in the given order, find i such that P_i=X.
Constraints
- 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) is a permutation of (1,2,\ldots,N).
- 1 \leq C_i \leq 2
- 1 \leq L_i \leq R_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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
Output
Print the answer.
Sample Input 1
5 2 1 1 4 5 2 3 1 3 5 2 1 3
Sample Output 1
3
Initially, the permutation is P=[1,4,5,2,3]. The queries change it as follows.
- 1-st query sorts the 3-rd through 5-th elements in ascending order, making P=[1,4,2,3,5].
- 2-nd query sorts the 1-st through 3-rd elements in descending order, making P=[4,2,1,3,5].
In the final permutation, we have P_3=1, so 3 should be printed.
Sample Input 2
7 3 3 7 5 3 1 2 4 6 1 1 7 2 3 6 2 5 7
Sample Output 2
7
The final permutation is P=[1,2,6,5,7,4,3].