题面
在摆烂了半年之后,小 ∆ 退化为了普及组选手,于是只能出一些普及组的题目,比如冒泡排序。他很好奇一个序列冒泡排序 $k$ 轮之后的样子。具体来讲,给定一个长度为 $n$ 的排列 $a_i$,他有两种询问:
给定 $l, r, k, x$ ,求将 $a_i$ 的区间 $[l, r]$ 冒泡排序 $k$ 轮之后,$x$ 这个数在 数组中的下标;
给定 $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$ | 无 |