L - 平均クエリ 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) と空の集合 S が与えられます。

また、0\leq L<R\leq N をみたす整数の組 (L,R) に対して、f(L,R) を \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} で定めます。

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

  • タイプ 1 : 0\leq x\leq N をみたす整数 x が与えられる。x が S に含まれないならば x を S に追加し、x が S に含まれるならば x を S から取り除く。
  • タイプ 2 : l,r\in S かつ 0\leq l<r\leq N をみたす整数の組 (l,r) すべてについての f(l,r) の最大値を X とする。このとき、X は互いに素な正整数 P, Q を用いて \frac{P}{Q} と一意に表される。P, Q を空白区切りで出力する。ただし、このクエリが与えられるとき、l,r\in S かつ 0\leq l<r\leq N をみたす (l,r) が少なくとも 1 つ存在することが保証される。

制約

  • 1\leq N\leq 10^5
  • 3\leq Q\leq 3\times 10^5
  • 1\leq A_i\leq 10^9
  • 0\leq x\leq N
  • 入力はすべて整数
  • タイプ 2 のクエリが少なくとも 1 つ存在する。
  • タイプ 2 のクエリを処理する時点において、l,r\in S かつ 0\leq l<r\leq N をみたす (l,r) が少なくとも 1 つ存在する。

入力

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

N Q
A_1 A_2 \ldots A_N
query_1
query_2
\vdots
query_Q

各 query_i において、まずクエリのタイプを表す番号 t_i (1\leq t_i\leq 2) が与えられる。 その後、t_i=1ならば整数 x (0\leq x\leq N) が与えられ、t_i=2 ならば何も与えられない。 すなわち、次のいずれかの形式で与えられる。

1 x

2

出力

与えられた Q 個のクエリのうち、タイプ 2 のクエリの個数を k として、k 行出力せよ。
i (1\leq i\leq k) 行目には、タイプ 2 のクエリのうち i 番目のものに対する答えを出力せよ。

入力例 1

3 8
2 3 5
1 0
1 3
2
1 2
2
1 1
1 3
2

出力例 1

10 3
5 1
3 1

f(L,R) の値は次のようになります。

  • f(0,1)=\frac{2}{1}=\frac{2}{1}
  • f(0,2)=\frac{2+3}{2}=\frac{5}{2}
  • f(0,3)=\frac{2+3+5}{3}=\frac{10}{3}
  • f(1,2)=\frac{3}{1}=\frac{3}{1}
  • f(1,3)=\frac{3+5}{2}=\frac{8}{2}
  • f(2,3)=\frac{5}{1}=\frac{5}{1}

クエリは次のように処理されます。

  • 1 番目のクエリはタイプ 1 であり、x=0 が与えられています。0\notin S であるため、S に 0 を追加します。
  • 2 番目のクエリでは、S に 3 を追加します。
  • 3 番目のクエリはタイプ 2 であり、この時点で S= \{ 0,3 \} であるため、l,r\in S かつ 0\leq l<r\leq N をみたす (l,r) は (0,3) のみです。 f(0,3)=\frac{10}{3} であるため、10, 3 を空白区切りに出力します。
  • 4 番目のクエリでは、S に 2 を追加します。
  • 5 番目のクエリの時点で S=\{0,2,3\} であり条件をみたす (l,r) は (0,2), (0,3), (2,3) の 3 つです。このうち f(l,r) が最大となるのは f(2,3)=\frac{5}{1} のときです。よって、5, 1 をこの順に出力します。
  • 6 番目のクエリでは、S に 1 を追加します。
  • 7 番目のクエリの直前の時点で 3\in S であるため、3 を S から取り除きます。
  • 8 番目のクエリの時点で S=\{ 0,1,2\} であり、条件をみたす (l,r) のうちで f(l,r) が最大となるのは f(1,2)=\frac{3}{1} のときです。よって、3, 1 をこの順に出力します。

入力例 2

2 3
1 1
1 0
1 2
2

出力例 2

1 1

タイプ 2 のそれぞれのクエリにおける P, Q は互いに素でなくてはならないことに注意してください。すなわち、このテストケースにおいて 2 2 と出力してはいけません。

Problem Statement

You are given a sequence of length N consisting of positive integers, A=(A_1,A_2,\ldots,A_N), and an empty set S.

Let us define f(L,R) as \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} for a pair of integers (L,R) such that 0\leq L<R\leq N.

Process Q queries in the given order. Each query is of one of the following two types.

  • Type 1 : You are given an integer x satisfying 0\leq x\leq N. If x is not in S, add x to S; otherwise, remove x from S.
  • Type 2 : Let X be the maximum value of f(l,r) over all pairs of integers (l,r) such that l,r\in S and 0\leq l<r\leq N. Then, X is uniquely represented as \frac{P}{Q} using positive integers P and Q that are coprime. Print P and Q separated by spaces. It is guaranteed that at the time this query is given, there is at least one pair (l,r) such that l,r\in S and 0\leq l<r\leq N.

Constraints

  • 1\leq N\leq 10^5
  • 3\leq Q\leq 3\times 10^5
  • 1\leq A_i\leq 10^9
  • 0\leq x\leq N
  • All input values are integers.
  • There is at least one query of type 2.
  • At the time of processing a query of type 2, there is at least one pair (l,r) such that l,r\in S and 0\leq l<r\leq N.

Input

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

N Q
A_1 A_2 \ldots A_N
query_1
query_2
\vdots
query_Q

Each query_i starts with a number t_i (1\leq t_i\leq 2) representing the type of the given query. It is followed by an integer x (0\leq x\leq N) if t_i=1, and nothing if t_i=2. That is, query_i is in one of the following formats:

1 x

2

Output

Print k lines, where k is the number of queries of type 2 among the given Q queries.
The i-th line (1\leq i\leq k) should contain the answer to the i-th query of type 2.

Sample Input 1

3 8
2 3 5
1 0
1 3
2
1 2
2
1 1
1 3
2

Sample Output 1

10 3
5 1
3 1

The values of f(L,R) are as follows.

  • f(0,1)=\frac{2}{1}=\frac{2}{1}
  • f(0,2)=\frac{2+3}{2}=\frac{5}{2}
  • f(0,3)=\frac{2+3+5}{3}=\frac{10}{3}
  • f(1,2)=\frac{3}{1}=\frac{3}{1}
  • f(1,3)=\frac{3+5}{2}=\frac{8}{2}
  • f(2,3)=\frac{5}{1}=\frac{5}{1}

The queries are processed as follows.

  • The first query is of type 1 and gives x=0. Since 0\notin S, add 0 to S.
  • The second query adds 3 to S.
  • The third query is of type 2, and we have S= \{ 0,3 \} at this point, so (0,3) is the only (l,r) such that l,r\in S and 0\leq l<r\leq N. We have f(0,3)=\frac{10}{3}, so print 10 and 3 separated by spaces.
  • The fourth query adds 2 to S.
  • At the time of the fifth query, we have S=\{0,2,3\}, and the pairs (l,r) that satisfy the condition are (0,2), (0,3), and (2,3). The maximum f(l,r) over these pairs is f(2,3)=\frac{5}{1}. Thus, print 5 and 1 in this order.
  • The sixth query adds 1 to S.
  • We have 3\in S just before the seventh query, so remove 3 from S.
  • At the time of the eighth query, we have S=\{ 0,1,2\}, and the maximum f(l,r) over the pairs satisfying the conditions is f(1,2)=\frac{3}{1}. Thus, print 3 and 1 in this order.

Sample Input 2

2 3
1 1
1 0
1 2
2

Sample Output 2

1 1

Note that P and Q in each query of type 2 must be coprime. That is, you must not print 2 2 in this test case.