← 返回题目列表

AtCoder · abc237_g

G. 范围排序查询

中文机器翻译题面 查看原题

分数: 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].