#4923. [Lydsy1706月赛]K小值查询

[Lydsy1706月赛]K小值查询

题目描述

维护一个长度为 nn 的正整数序列 a1,a2,,ana_1,a_2,\dots,a_n,支持以下两种操作:

  1. 1 k1~k,将序列 aa 从小到大排序,输出 aka_k 的值。
  2. 2 k2~k,将所有严格大于 kk 的数 aia_i 减去 kk

输入格式

第一行包含两个正整数 nnmm,分别表示序列的长度和操作的个数。

第二行包含 nn 个正整数 a1,a2,,ana_1,a_2,\dots,a_n,分别表示序列中的每个元素。

接下来 mm 行,每行两个正整数 opopkk,依次描述每个操作。

输出格式

输出若干行,对于每个询问输出一行一个整数,即第 kk 小的值。

4 5
1 5 6 12
2 5
1 1
1 2
1 3
1 4
1
1
5
7

数据范围

1n,m105, 1ai109,op1, 21 \le n,m \le 10^5,~1 \le a_i \le 10^9,op \in {1,~2}

op=1op = 11kn1 \le k \le n
op=2op = 21k1091 \le k \le 10^9