C - Max - Min Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数の多重集合 S があります。はじめ S は空です。

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

  • 1 x : S に x を 1 個追加する。

  • 2 x c : S から x を \mathrm{min}(c, (S に含まれる x の個数 )) 個削除する。

  • 3 : (S の最大値 )- (S の最小値 ) を出力する。このクエリを処理するとき、 S が空でないことが保証される。

制約

  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq x \leq 10^9
  • 1 \leq c \leq Q
  • 3 のクエリを処理するとき、S は空でない。
  • 入力は全て整数

入力

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

Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

i 番目のクエリを表す \mathrm{query}_i は以下の 3 種類のいずれかである。

1 x

2 x c

3

出力

3 のクエリに対する答えを順に改行区切りで出力せよ。

入力例 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

出力例 1

1
5
4

多重集合 S は以下のように変化します。

  • 1 番目のクエリ : S に 3 を追加する。S は \lbrace3 \rbrace となる。
  • 2 番目のクエリ : S に 2 を追加する。S は \lbrace2, 3\rbrace となる。
  • 3 番目のクエリ : S = \lbrace 2, 3\rbrace の最大値は 3 、最小値は 2 なので、 3-2=1 を出力する。
  • 4 番目のクエリ : S に 2 を追加する。S は \lbrace2,2,3 \rbrace となる。
  • 5 番目のクエリ : S に 7 を追加する。S は \lbrace2, 2,3, 7\rbrace となる。
  • 6 番目のクエリ : S = \lbrace2,2,3, 7\rbrace の最大値は 7 、最小値は 2 なので、 7-2=5 を出力する。
  • 7 番目のクエリ : S に含まれる 2 の個数は 2 個なので、 \mathrm{min(2,3)} = 2 個の 2 を S から削除する。S は \lbrace3, 7\rbrace となる。
  • 8 番目のクエリ : S = \lbrace3, 7\rbrace の最大値は 7 、最小値は 3 なので、 7-3=4 を出力する。

入力例 2

4
1 10000
1 1000
2 100 3
1 10

出力例 2



クエリ 3 が含まれない場合、何も出力してはいけません。






Score : 300 points







Problem Statement
We have a multiset of integers S, which is initially empty.


Given Q queries, process them in order.
Each query is of one of the following types.


    

  • 

    1 x: Insert an x into S.
    

    • 

  • 

    2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).
    

    • 

  • 

    3 : Print ( maximum value of S)-( minimum value of S).  It is guaranteed that S is not empty when this query is given.
    

    • 












Constraints
    

  • 1 \leq Q \leq 2\times 10^5
    • 

  • 0 \leq x \leq 10^9
    • 

  • 1 \leq c \leq Q
    • 

  • When a query of type 3 is given, S is not empty.
    • 

  • All values in input are integers.
    • 
















Input
Input is given from Standard Input in the following format:


Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q



\mathrm{query}_i, which denotes the i-th query, is in one of the following formats:


1 x



2 x c



3 












Output
Print the answers for the queries of type 3 in the given order, separated by newlines.















Sample Input 1
8
1 3
1 2
3
1 2
1 7
3
2 2 3
3












Sample Output 1
1
5
4



The multiset S transitions as follows.


    

  • 1-st query: insert 3 into S.  S is now \lbrace 3 \rbrace.
    • 

  • 2-nd query: insert 2 into S.  S is now \lbrace 2, 3 \rbrace.
    • 

  • 3-rd query: the maximum value of S = \lbrace  2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
    • 

  • 4-th query: insert 2 into S.  S is now \lbrace 2,2,3 \rbrace.
    • 

  • 5-th query: insert 7 into S.  S is now \lbrace 2, 2,3, 7\rbrace.
    • 

  • 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
    • 

  • 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice.  S is now \lbrace 3, 7\rbrace.
    • 

  • 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.
    • 














Sample Input 2
4
1 10000
1 1000
2 100 3
1 10












Sample Output 2


If the given queries do not contain that of type 3, nothing should be printed.