長さ $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$ 行ずつ出力してください。
最後に改行してください。
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$ を出力してください。
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)$ になりなす。
1000000000000 2
500000000000 500000000000
3
2 2 500000000000
2 1 499999999999
3 0 0
1
配列 $A$ が空になることはありません。
source: No.1705 Mode of long array
最終更新日: 2022/2/15 17:26:36