Range k-th Largest Query

2 secs 1024 MB
VvyLw's icon VvyLw

問題

要素数が NN の配列 AA がある。この配列に対して QQ 個のクエリが与えられるので順に処理せよ。
クエリは以下の通りである。

  • 1 x : AA の全ての要素に対して xx だけ加算する。
  • 2 l r k: 閉区間 [l,r][l,r] での AAkk 番目に大きい値を出力する。

制約

  • 1N, Q1051 \le N,\ Q \le 10^5
  • 109Ai(1iN), x109-10^9 \le A_i(1 \le i \le N),\ x \le 10^9
  • 1l, rN1 \le l,\ r \le N
  • 1krl+11 \le k \le r - l + 1
  • N, Q, Ai, x, l, r, kZN,\ Q,\ A_i,\ x,\ l,\ r,\ k \in \Z

入力

N QN\ Q
A1 A2 ... AnA_1\ A_2\ ...\ A_n
Query1Query_1
Query2Query_2
......
QueryQQuery_Q

ただし、QueryqQuery_q は以下のいずれかの形式で与えられる。

1 x1\ x

2 l r k2\ l\ r\ k

出力

2番目の形式のクエリに対し、答えを出力せよ。また、クエリごとに改行せよ。

入力例 1

5 4
2 7 1 8 2
1 4
2 1 3 2
1 -7
2 3 5 1

出力例 1

6
5

Query1Query_1: AA の要素全てに4を加える。A=[6,11,5,12,6]A = [6, 11, 5, 12, 6]
Query2Query_2: AA の部分配列 A[1..3]=[6,11,5]A[1..3] = [6, 11, 5] , ここで2番目に大きいのは6
Query3Query_3: AA の要素全てに7を引く。A=[1,4,2,5,1]A = [-1, 4, -2, 5, -1]
Query4Query_4: AA の部分配列 A[3..5]=[2,5,1]A[3..5] = [-2, 5, -1] , ここで1番目に大きいのは5

入力例 2

6 3
1 2 3 4 5 6
2 1 4 2
1 -7
2 3 5 3

出力例 2

3
-4

入力例 3

3 11
1000000000 1000000000 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1 1 1

出力例 3

11000000000

答えは32-bit整数で収まらないことに注意せよ。

提出


Go (1.21)