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

    ID: 4028 传统题 1000ms 512MiB 尝试: 784 已通过: 153 难度: 7 上传者: 标签>CF2300提高+/省选-FHQ Treap 分裂合并维护顺序统计量标记复合势能分析本OJ付费获取

[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。

输入格式

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

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

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

输出格式

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

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

数据范围

$1 \le n,m \le 10^5,~1 \le a_i \le 10^9,op \in {1,~2}$

当 op=1op = 1 时 1≤k≤n1 \le k \le n。 当 op=2op = 2 时 1≤k≤1091 \le k \le 10^9。