Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
Statistics

题面

在摆烂了半年之后,小 ∆ 退化为了普及组选手,于是只能出一些普及组的题目,比如冒泡排序。他很好奇一个序列冒泡排序 $k$ 轮之后的样子。具体来讲,给定一个长度为 $n$ 的排列 $a_i$,他有两种询问:

  1. 给定 $l, r, k, x$ ,求将 $a_i$ 的区间 $[l, r]$ 冒泡排序 $k$ 轮之后,$x$ 这个数在 数组中的下标;

  2. 给定 $l, r, k, x$ ,求将 $a_i$ 的区间 $[l, r]$ 冒泡排序 $k$ 轮之后,$a_x$ 的值。

小 ∆ 在每次询问后都会将序列复原。也就是说询问相互独立。

定义对 ai 的区间 $[l, r]$ 进行一轮冒泡排序为依次对于 $i = l, l+ 1, \cdots , r−1$,若 $a_i$ > $a_{i+1}$,则交换 $a_i, a_{i+1}$

输入格式

第一行,三个正整数 $n, q, o$,其中 $q$ 为询问的个数;$o$ 代表询问的种类,$o = 1, 2$ 分别代表小 ∆ 的询问全是第一、二种的。

第二行,$n$ 个正整数,$a_i$

接下来 $q$ 行,每行四个非负整数 $l, r, k, x$,代表一组询问。

输出格式

$q$ 行,每行一个正整数,对应询问的答案。

样例 1

输入

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

输出

3
1
2
1

样例解释

区间 $[1, 4]$ 进行两轮冒泡排序之后,序列变为 $2, 1, 3, 4$

区间 $[1, 3]$ 进行一轮冒泡排序之后,序列变为 $3, 2, 4, 1$

区间 $[2, 4]$ 进行一轮冒泡排序之后,序列变为 $3, 2, 1, 4$

样例 2

输入

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

输出

3
1
2
1

样例 3

见下发文件,此样例满足子任务 $1$ 的限制。

样例 4

见下发文件,此样例满足子任务 $1$ 的限制。

样例 5

见下发文件,此样例满足子任务 $4$ 的限制。

样例 6

见下发文件,此样例满足子任务 $5$ 的限制。

数据范围与限制

对于所有数据 $1\le n,q\le 6\times10^5,o\in\{1,2\},1\le l\le r\le n,1\le x\le n,0\le k\le n-1$,保证 $a_i$ 是 $1, 2, \cdots , n$ 的一个排列。

子任务如下:

子任务编号 分值 $n,q\le$ 特殊性质
$1$ $10$ $500$
$2$ $5$ $7000$ $o=1$
$3$ $5$ $7000$ $o=2$
$4$ $10$ $10^5$ $o=1$
$5$ $10$ $10^5$ $o=2$
$6$ $10$ $10^5$
$7$ $20$ $6\times10^5$ $o=1$
$8$ $20$ $6\times10^5$ $o=2$
$9$ $10$ $6\times10^5$