分数: 600 点
问题陈述
给定的是一个排列 P=(P_1,P_2,\ldots,P_N) of 1,2,\ldots,N,和一个整数 X.
此外, 给出了 Q 查询。 的 i-第一个查询表示为三个数字 (C_i,L_i,R_i)。每个查询对排列执行以下操作 P.
- If C_i=1:排序 P_{L_i},P_{L_i+1},\ldots,P_{R_i} 按升序排列。
- If C_i=2:排序 P_{L_i},P_{L_i+1},\ldots,P_{R_i} 按降序排列。
在最终的排列中 P 按给定顺序执行所有查询后,找到 i 这样 P_i=X.
约束
- 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-st 查询对 3-rd 通过 5- 第一个元素按升序排列,使得 P=[1,4,2,3,5].
- 2-nd 查询对 1-st 通过 3-rd 元素按降序排列,使得 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].