P13981 数列分块入门 6
题目描述
给出一个长度为 n 的数列 {a1,a2,…,an},以及与初始长度相同的 n 次操作。操作只有单点插入与单点询问两种。
所有操作依次作用在当前的数列上。记某次操作前数列中数字的个数为 len,则:
∙若 opt=0,在第 l 个数前插入数字 r。特别地,当 l=len+1 时,相当于把 r 追加到数列末尾;
∙若 opt=1,询问当前数列中第 c 个数的值。
本题的测试数据随机生成:每次操作先以相等的概率随机决定 opt 为 0 或 1,再在所有合法的取值中均匀等概率地随机抽取其余参数。
输入格式
第一行输入一个整数 n(1≦n≦3×105) 代表数列的初始长度,同时也代表操作的次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i \leqq 2^{31} - 1\right)$ 代表数列的初始元素。
此后 n 行,每行输入一个操作。每行先输入一个整数 $\mathrm{opt} \left(0 \leqq \mathrm{opt} \leqq 1\right)$ 代表操作类型,随后在同一行:
∙若 opt=0,输入两个整数 $l, r \left(1 \leqq l \leqq \mathrm{len}+1;\ -2^{31} \leqq r \leqq 2^{31} - 1\right)$ 代表在第 l 个数前插入数字 r;
∙若 opt=1,输入一个整数 c(1≦c≦len) 代表询问的数在数列中的位置。
其中,len 代表该次操作前数列中数字的个数。
输出格式
对于每次询问,在一行上输出一个整数,代表当前数列中第 c 个数的值。
测试样例
4
1 2 2 3
0 1 3
1 4
0 1 2
1 2
2
3
样例 1 解释
初始数列为 {1,2,2,3},操作过程如下:
∙执行 "0 1 3":在第 1 个数前插入 3,数列变为 {3,1,2,2,3};
∙执行 "1 4":询问第 4 个数,得到 2;
∙执行 "0 1 2":在第 1 个数前插入 2,数列变为 {2,3,1,2,2,3};
∙执行 "1 2":询问第 2 个数,得到 3。
因此依次输出 2 与 3。
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 解释
初始数列为 {5,1,4,2,3,6},操作过程如下:
∙执行 "1 3":询问第 3 个数,得到 4;
∙执行 "0 2 7":在第 2 个数前插入 7,数列变为 {5,7,1,4,2,3,6};
∙执行 "1 4":询问第 4 个数,得到 4;
∙执行 "0 7 8":在第 7 个数前插入 8,数列变为 {5,7,1,4,2,3,8,6};
∙执行 "1 5":询问第 5 个数,得到 2;
∙执行 "1 1":询问第 1 个数,得到 5。
因此依次输出 4,4,2,5。
提示
子任务
子任务 1(40 分):1≦n≦105,−231≦ai,r≦231−1。
子任务 2(60 分):1≦n≦3×105,−231≦ai,r≦231−1。
对于全部数据,1≦n≦3×105,−231≦ai,r≦231−1,0≦opt≦1,且 1≦l≦len+1、1≦c≦len。
测试数据保证:每次询问先均匀等概率生成 opt 为 0 或 1 的情形,其余询问参数在所有合法的取值中随机均匀等概率抽取。