Range Sort Query

题目描述

给定一个长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，它是 $1,2,\ldots,N$ 的一个排列。同时给定一个整数 $X$。

接下来有 $Q$ 个查询。第 $i$ 个查询由三个整数 $(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}$ 按降序排序。

按照给定顺序处理完所有查询后，求最终排列中满足 $P_i=X$ 的下标 $i$。

输入格式

输入从标准输入给出，格式如下：

N Q X
P_1 P_2 ... P_N
C_1 L_1 R_1
C_2 L_2 R_2
...
C_Q L_Q R_Q

输出格式

输出最终排列中元素 $X$ 所在的位置。

数据范围

• $1 \le N \le 2\times 10^5$
• $1 \le Q \le 2\times 10^5$
• $1 \le X \le N$
• $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。
• $1 \le C_i \le 2$
• $1 \le L_i \le R_i \le N$
• 输入均为整数。

样例

样例输入 1

5 2 1
1 4 5 2 3
1 3 5
2 1 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

样例说明

样例 1 中，初始排列为 $[1,4,5,2,3]$。

• 第一次查询将第 $3$ 到第 $5$ 个元素升序排序，排列变为 $[1,4,2,3,5]$；
• 第二次查询将第 $1$ 到第 $3$ 个元素降序排序，排列变为 $[4,2,1,3,5]$。

最终 $P_3=1$，因此输出 $3$。

样例 2 中，最终排列为 $[1,2,6,5,7,4,3]$，元素 $3$ 在位置 $7$。