LG#P13981. 数列分块入门 6

数列分块入门 6

P13981 数列分块入门 6

题目描述

\hspace{15pt}给出一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及与初始长度相同的 nn 次操作。操作只有单点插入与单点询问两种。

\hspace{15pt}所有操作依次作用在当前的数列上。记某次操作前数列中数字的个数为 len\mathrm{len},则:

∙ \hspace{23pt}\bullet\,若 opt=0\mathrm{opt} = 0,在第 ll 个数前插入数字 rr。特别地,当 l=len+1l = \mathrm{len}+1 时,相当于把 rr 追加到数列末尾;

∙ \hspace{23pt}\bullet\,若 opt=1\mathrm{opt} = 1,询问当前数列中第 cc 个数的值。

\hspace{15pt}本题的测试数据随机生成:每次操作先以相等的概率随机决定 opt\mathrm{opt} 为 00 或 11,再在所有合法的取值中均匀等概率地随机抽取其余参数。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×105)n \left(1 \leqq n \leqq 3 \times 10^5\right) 代表数列的初始长度,同时也代表操作的次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i \leqq 2^{31} - 1\right)$ 代表数列的初始元素。

\hspace{15pt}此后 nn 行,每行输入一个操作。每行先输入一个整数 $\mathrm{opt} \left(0 \leqq \mathrm{opt} \leqq 1\right)$ 代表操作类型,随后在同一行:

∙ \hspace{23pt}\bullet\,若 opt=0\mathrm{opt} = 0,输入两个整数 $l, r \left(1 \leqq l \leqq \mathrm{len}+1;\ -2^{31} \leqq r \leqq 2^{31} - 1\right)$ 代表在第 ll 个数前插入数字 rr;

∙ \hspace{23pt}\bullet\,若 opt=1\mathrm{opt} = 1,输入一个整数 c(1≦c≦len)c \left(1 \leqq c \leqq \mathrm{len}\right) 代表询问的数在数列中的位置。

\hspace{15pt}其中,len\mathrm{len} 代表该次操作前数列中数字的个数。

输出格式

\hspace{15pt}对于每次询问,在一行上输出一个整数,代表当前数列中第 cc 个数的值。

测试样例

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

样例 1 解释

\hspace{15pt}初始数列为 {1,2,2,3}\{1, 2, 2, 3\},操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "0 1 3"\texttt{"0 1 3"}:在第 11 个数前插入 33,数列变为 {3,1,2,2,3}\{3, 1, 2, 2, 3\};

∙ \hspace{23pt}\bullet\,执行 "1 4"\texttt{"1 4"}:询问第 44 个数,得到 22;

∙ \hspace{23pt}\bullet\,执行 "0 1 2"\texttt{"0 1 2"}:在第 11 个数前插入 22,数列变为 {2,3,1,2,2,3}\{2, 3, 1, 2, 2, 3\};

∙ \hspace{23pt}\bullet\,执行 "1 2"\texttt{"1 2"}:询问第 22 个数,得到 33。

\hspace{15pt}因此依次输出 22 与 33。

6
5 1 4 2 3 6
1 3
0 2 7
1 4
0 7 8
1 5
1 1
4
4
2
5

样例 2 解释

\hspace{15pt}初始数列为 {5,1,4,2,3,6}\{5, 1, 4, 2, 3, 6\},操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "1 3"\texttt{"1 3"}:询问第 33 个数,得到 44;

∙ \hspace{23pt}\bullet\,执行 "0 2 7"\texttt{"0 2 7"}:在第 22 个数前插入 77,数列变为 {5,7,1,4,2,3,6}\{5, 7, 1, 4, 2, 3, 6\};

∙ \hspace{23pt}\bullet\,执行 "1 4"\texttt{"1 4"}:询问第 44 个数,得到 44;

∙ \hspace{23pt}\bullet\,执行 "0 7 8"\texttt{"0 7 8"}:在第 77 个数前插入 88,数列变为 {5,7,1,4,2,3,8,6}\{5, 7, 1, 4, 2, 3, 8, 6\};

∙ \hspace{23pt}\bullet\,执行 "1 5"\texttt{"1 5"}:询问第 55 个数,得到 22;

∙ \hspace{23pt}\bullet\,执行 "1 1"\texttt{"1 1"}:询问第 11 个数,得到 55。

\hspace{15pt}因此依次输出 4,4,2,54, 4, 2, 5。

提示

子任务

\hspace{15pt}子任务 1(40 分):1≦n≦1051 \leqq n \leqq 10^5,−231≦ai,r≦231−1-2^{31} \leqq a_i, r \leqq 2^{31} - 1。

\hspace{15pt}子任务 2(60 分):1≦n≦3×1051 \leqq n \leqq 3 \times 10^5,−231≦ai,r≦231−1-2^{31} \leqq a_i, r \leqq 2^{31} - 1。

\hspace{15pt}对于全部数据,1≦n≦3×1051 \leqq n \leqq 3 \times 10^5,−231≦ai,r≦231−1-2^{31} \leqq a_i, r \leqq 2^{31} - 1,0≦opt≦10 \leqq \mathrm{opt} \leqq 1,且 1≦l≦len+11 \leqq l \leqq \mathrm{len}+1、1≦c≦len1 \leqq c \leqq \mathrm{len}。

\hspace{15pt}测试数据保证:每次询问先均匀等概率生成 opt\mathrm{opt} 为 00 或 11 的情形,其余询问参数在所有合法的取值中随机均匀等概率抽取。