BZPRO
#4923. [Lydsy1706月赛]K小值查询
内存限制：256 MiB
时间限制：15 Sec
提交
提交记录
讨论
题目描述
维护一个长度为n的正整数序列a_1,a_2,...,a_n，支持以下两种操作：
1 k，将序列a从小到大排序，输出a_k的值。
2 k，将所有严格大于k的数a_i减去k。
输入格式
第一行包含两个正整数n,m(1<=n,m<=100000)，分别表示序列的长度和操作的个数。
第二行包含n个正整数a_1,a_2,...,a_n(1<=a_i<=10^9)，分别表示序列中的每个元素。
接下来m行，每行两个正整数op(1<=op<=2),k，若op=1，则1<=k<=n；若op=2，则1<=k<=10^9；依次描述每个操作。
输出格式
输出若干行，对于每个询问输出一行一个整数，即第k小的值。
样例
样例输入
4 5
1 5 6 12
2 5
1 1
1 2
1 3
1 4
样例输出
1
1
5
7
数据范围与提示
BZPRO