問題一覧 > 通常問題

No.1705 Mode of long array

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 115
作問者 : harurunharurun / テスター : yuusanlondonyuusanlondon
2 ProblemId : 7027 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-08 23:03:54

問題文

長さ $N$ の配列 $A$ があり、配列 $A$ には $1$ 以上 $M$ 以下の整数 $i$ が $a_i$ 個 あります。

クエリが $Q$ 個与えられるので、順に処理してください。 $i$ 番目のクエリでは $T_i,X_i,Y_i$ が与えれます。

  • $T_i=1$ のとき

  • 配列 $A$ に整数 $X_i$ を $Y_i$ 個追加する。

  • $T_i=2$ のとき

  • 配列 $A$ から整数 $X_i$ を $Y_i$ 個取り除く。ただし、このとき配列 $A$ に整数 $X_i$ が $Y_i$ 個以上あることが保証される。

  • $T_i=3$ のとき

  • 配列 $A$ の最頻値を出力する。ただし、最頻値が複数ある場合はその中で最大の値を出力する。

入力

$N\ M$
$a_1 \ldots a_M$
$Q$
$T_1\ X_1\ Y_1$
$\vdots$
$T_Q\ X_Q\ Y_Q$
  • $1$ 行目に $N$ と $M$ が空白区切りで与えられる

  • $2$ 行目に $a_i$ が空白区切りで与えられる

  • $3$ 行目に $Q$ が与えれられる

  • $4\sim Q+3$ 行目に $T_i,X_i,Y_i$ が空白区切りで与えられる

制約

  • $1≤N≤5\times 10^{17}$

  • $1≤M≤10^5$

  • $0≤a_i≤N$

  • $\sum_{i=1}^{M}a_i=N$

  • $1≤Q≤10^5$

  • $1≤T_i≤3$

  • $T_i=1$ のとき

    • $1≤X_i≤M$

    • $1≤Y_i≤10^{12}$

  • $T_i=2$ のとき

    • $1≤X_i≤M$

    • $1≤Y_i≤10^{12}$

    • 取り除くとき、配列 $A$ に整数 $X_i$ が $Y_i$ 個以上含まれる

  • $T_i=3$ のとき

    • $X_i=Y_i=0$ (この $X_i,Y_i$ は問題には使用されない)

  • $T_i=3$ のクエリが少なくとも $1$ 個含まれる

  • 配列 $A$ が空になるようなテストケースは与えられない

  • 入力は全て整数である

出力

$T_i=3$ であるような各クエリについてそれぞれ $1$ 行ずつ出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3
1 1 1
10
1 1 5
3 0 0
1 2 8
3 0 0
1 3 2
3 0 0
1 1 10
3 0 0
1 2 7
3 0 0
出力
1
2
2
1
2

最初 $A=(1,2,3)$ です。

$1$ 個目のクエリで $A=(1,1,1,1,1,1,2,3)$ になります。

$2$ 個目のクエリでは $A$ の最頻値の $1$ を出力してください。

$3$ 個目のクエリで $A=(1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3)$ になりなす。

$4$ 個目のクエリでは $A$ の最頻値の $2$ を出力してください。

$5$ 個目のクエリで $A=(1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3)$ になりなす。

$6$ 個目のクエリでは $A$ の最頻値の $2$ を出力してください。

$7$ 個目のクエリで $A=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3)$ になりなす。

$8$ 個目のクエリでは $A$ の最頻値の $1$ を出力してください。

$9$ 個目のクエリで $A=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3)$ になりなす。

$10$ 個目のクエリでは $A$ の最頻値は $1,2$ です。大きいほうの $2$ を出力してください。

サンプル2
入力
25 3
10 10 5
16
3 0 0
1 3 4
2 1 1
3 0 0
2 2 1
3 0 0
1 2 1
3 0 0
1 1 2
3 0 0
1 2 3
3 0 0
2 1 5
3 0 0
2 2 5
3 0 0
出力
2
2
3
2
1
2
2
3

最終的に $A=(1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3)$ になりなす。

サンプル3
入力
1000000000000 2
500000000000 500000000000
3
2 2 500000000000
2 1 499999999999
3 0 0
出力
1

配列 $A$ が空になることはありません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。