K - Multiset Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

整数の多重集合 S があります。はじめ、S は N 個の要素 A_1,A_2,\ldots,A_N をもっています。

クエリを Q 個処理してください。クエリは以下の 3 種類のいずれかです。

  • 1 x：S に x を 1 個追加する。
  • 2 x：S から x を 1 個削除する。このクエリを処理する直前の S には、x が 1 個以上含まれることが保証される。
  • 3：S の要素を重複を含めて昇順に並べた列を x_1,x_2,\ldots,x_k とする。このとき、\displaystyle \sum_{i=1}^{k} i x_i を 998244353 で割った余りを出力する。

S が空であるときは k=0 であり、上記の和を 0 とします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 種類目および 2 種類目のクエリについて、0 \leq x \leq 10^9
  • 2 種類目のクエリを処理する直前の S には、x が 1 個以上含まれる
  • 入力される数値はすべて整数

入力

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

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 x

2 x

3

出力

3 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 3 種類目のクエリに対する答えを出力せよ。

入力例 1

4 8
3 1 3 2
3
1 0
3
2 3
3
2 3
3
1 2

出力例 1

26
35
20
8

はじめの S の要素を昇順に並べると (1,2,3,3) なので、最初のクエリでは 1 \times 1+2 \times 2+3 \times 3+4 \times 3=26 を出力します。

入力例 2

1 5
998244353
3
2 998244353
3
1 1000000000
3

出力例 2

0
0
1755647

3 番目のクエリでは、その時点では S は空なので、0 を出力します。

Score: 4 points

Problem Statement

There is a multiset S of integers. Initially, S has N elements A_1,A_2,\ldots,A_N.

Process Q queries. Each query is of one of the following 3 types:

  • 1 x: Add 1 occurrence of x to S.
  • 2 x: Remove 1 occurrence of x from S. It is guaranteed that immediately before this query is processed, S contains at least 1 occurrence of x.
  • 3: Let x_1,x_2,\ldots,x_k be the sequence obtained by sorting all elements of S in ascending order, including duplicates. Print \displaystyle \sum_{i=1}^{k} i x_i modulo 998244353.

When S is empty, k=0, and the sum above is defined to be 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • For queries of types 1 and 2, 0 \leq x \leq 10^9
  • Immediately before each type 2 query, S contains at least 1 occurrence of x.
  • All numerical values in the input are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 x

2 x

3

Output

Let q be the number of type 3 queries. Print q lines. The j-th line should contain the answer to the j-th type 3 query.

Sample Input 1

4 8
3 1 3 2
3
1 0
3
2 3
3
2 3
3
1 2

Sample Output 1

26
35
20
8

Sorting the initial elements of S in ascending order gives (1,2,3,3), so for the first query, print 1 \times 1+2 \times 2+3 \times 3+4 \times 3=26.

Sample Input 2

1 5
998244353
3
2 998244353
3
1 1000000000
3

Sample Output 2

0
0
1755647

For query 3, S is empty at that time, so print 0.