← 返回题目列表

AtCoder · past202203_m

M. 排名

中文机器翻译题面 查看原题

分数: 6 点

问题陈述

N 名为 Player 的玩家 1,玩家 2, \ldots,玩家 N 正在玩游戏。玩家的初始分数 i is P_i 点。

流程 Q 按给出的顺序进行查询。 查询分为以下三种。

  • 1 a x: 改变玩家的分数 a to x.
  • 2 a: 打印玩家当前排名 a 其中 N 玩家。具体来说,如果玩家 a 有 r- 第最高分,打印整数 r.
  • 3 r: 打印当前排名的玩家 r-th。具体来说,如果玩家 a 有 r- 第最高分,打印整数 a.

这里,保证玩家的初始分数和作为第一类查询给出的改变之后的分数都是不同的。

约束

  • 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
  • 全部 x 在第一类查询中与所有查询都是不同的 P_i.
  • 至少有一个第二类或第三类查询。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

每个 query_i 在 3-rd 通过 (Q+2)第行以下列格式之一给出:

1 a x
2 a
3 r

输出

按照给出的顺序打印对第二类和第三类查询的响应,并用换行符分隔。


示例输入 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 点。

  • 对于第一个查询,Player 1 得分第三高,因此 3 。
  • 对于第二个查询,Player 2 得分第一,因此 2 。
  • 第三次查询中,Player的得分 2 更改为 0。现在,玩家 1,玩家 2,玩家 3 有 分别为 10, 0, 20 点。
  • 对于第四个查询,Player 1 得分第二高,因此 2 。
  • 对于第五个查询,Player 1 得分第二高,因此 1 。