AT_abc237_g [ABC237G] Range Sort Query

题目描述

给定一个由 $1,2,\ldots,N$ 组成的长度为 $N$ 的排列 $P=(P_1,P_2,\ldots,P_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$ $\ldots$ $P_N$
$C_1$ $L_1$ $R_1$
$C_2$ $L_2$ $R_2$
$\vdots$
$C_Q$ $L_Q$ $R_Q$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

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$
• 输入均为整数。

样例解释 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$。

样例解释 2

最终排列为 $P=[1,2,6,5,7,4,3]$。

由 ChatGPT 4.1 翻译