M - Ranking Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

選手 1 、選手 2 、\ldots 、選手 N の N 人の選手がゲームをしており、 選手 i の得点は最初 P_i 点です。

クエリが Q 個与えられるので、与えられた順番に処理してください。 クエリは次の 3 種類のいずれかです。

  • 1 a x : 選手 a の得点を x に変更する。
  • 2 a : 現在の選手 a の得点が、N 人のうち大きい方から何番目か出力する。具体的には r 番目であるとき整数 r を出力する。
  • 3 r : N 人のうち現在の得点が大きい方から r 番目の選手を出力する。具体的には選手 a が r 番目であるとき整数 a を出力する。

ただし、最初に与えられる各選手の得点および、 1 つめの種類のクエリで与えられる変更後の選手の得点はすべて相異なることが保証されます。

制約

  • 1 \leq N,Q \leq 5\times 10^5
  • 0\leq P_i \leq 10^9
  • P_i \neq P_j (i\neq j)
  • 1\leq a \leq N
  • 0\leq x \leq 10^9
  • 1\leq r \leq N
  • 1 つめの種類のクエリの x はすべて互いに相異なり、また P_i のいずれとも相異なる。
  • 2 つめまたは 3 つめの種類のクエリが 1 つ以上存在する。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
P_1 P_2 \ldots P_N
query_1
query_2
\vdots
query_Q

3 行目から Q+2 行目の各 query_i は次のいずれかの形で与えられる。 

1 a x

2 a

3 r

出力

2 つめおよび 3 つめの種類のクエリに対する出力を、 与えられた順に改行区切りで出力せよ。

入力例 1

3 5
10 30 20
2 1
3 1
1 2 0
2 1
3 2

出力例 1

3
2
2
1

最初、選手 1 、選手 2 、選手 3 の得点はそれぞれ 10 , 30 , 20 です。

  • 1 つめのクエリについて、選手 1 の得点は 3 番目に大きいので 3 を出力します。
  • 2 つめのクエリについて、1 番目に得点が大きい選手は選手 2 であるので 2 を出力します。
  • 3 つめのクエリによって、選手 2 の得点は 0 に変更されます。 これによって選手 1 、選手 2 、選手 3 の得点はそれぞれ 10 , 0 , 20 になります。
  • 4 つめのクエリについて、選手 1 の得点は 2 番目に大きいので 2 を出力します。
  • 5 つめのクエリについて、2 番目に得点が大きい選手は選手 1 であるので 1 を出力します。

Score : 6 points

Problem Statement

N players called Player 1, Player 2, \ldots, Player N are playing a game. The initial score of Player i is P_i points.

Process Q queries in the order they are given. There are three kinds of queries, as follows.

  • 1 a x: Change the score of Player a to x.
  • 2 a: Print the current rank of Player a among the N players. Specifically, if Player a has the r-th highest score, print the integer r.
  • 3 r: Print the player who currently ranks r-th. Specifically, if Player a has the r-th highest score, print the integer a.

Here, it is guaranteed that the initial scores of the players, and the scores after the changes given as queries of the first kind, are all distinct.

Constraints

  • 1 \leq N,Q \leq 5\times 10^5
  • 0\leq P_i \leq 10^9
  • P_i \neq P_j (i\neq j)
  • 1\leq a \leq N
  • 0\leq x \leq 10^9
  • 1\leq r \leq N
  • All x in the queries of the first kind are distinct and different from all of P_i.
  • There is at least one query of the second or third kind.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
P_1 P_2 \ldots P_N
query_1
query_2
\vdots
query_Q

Each query_i in the 3-rd through (Q+2)-th lines is given in one of the following formats:

1 a x

2 a

3 r

Output

Print the response to the queries of the second and third kinds, in the order they are given, separated by newlines.

Sample Input 1

3 5
10 30 20
2 1
3 1
1 2 0
2 1
3 2

Sample Output 1

3
2
2
1

Initially, Player 1, Player 2, Player 3 has 10, 30, 20 points, respectively.

  • For the first query, Player 1 has the third highest score, so 3 should be printed.
  • For the second query, Player 2 has the first highest score, so 2 should be printed.
  • In the third query, the score of Player 2 is changed to 0. Now, Player 1, Player 2, Player 3 has 10, 0, 20 points, respectively.
  • For the fourth query, Player 1 has the second highest score, so 2 should be printed.
  • For the fifth query, Player 1 has the second highest score, so 1 should be printed.