← 返回题目列表

AtCoder · past202309_l

L. 平均查询

中文机器翻译题面 查看原题

问题陈述

给你一个长度序列 N 由正整数组成, A=(A_1,A_2,\ldots,A_N)和一个空集 S.

让我们定义 f(L,R) as \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} 为一对整数 (L,R) 这样 0\leq L<R\leq N.

流程 Q 按给定顺序查询。 每个查询属于以下两种类型之一。

  • 类型 1 :给你一个整数 x 满意 0\leq x\leq N。如果 x 不在 S,添加 x to S;否则,删除 x 来自 S.
  • 类型 2 :让 X 是最大值 f(l,r) 所有整数对 (l,r) 这样 l,r\in S 和 0\leq l<r\leq N。然后, X 唯一表示为 \frac{P}{Q} 使用正整数 P 和 Q 是互质的。打印 P 和 Q 以空格分隔。保证在给出这个查询时,至少有一对 (l,r) 这样 l,r\in S 和 0\leq l<r\leq N.

约束

  • 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.
  • 在处理类型的查询时 2,至少有一对 (l,r) 这样 l,r\in S 和 0\leq l<r\leq N.

输入

输入由标准输入按以下格式给出:

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) 表示给定查询的类型。 后面跟着一个整数 x (0\leq x\leq N) if t_i=1,如果 t_i=2。 也就是说, query_i 采用以下格式之一:

1 x
2

输出

打印 k 行,其中 k 是该类型的查询数 2 其中给定 Q 查询。
的 i第行 (1\leq i\leq k) 应包含以下问题的答案 i类型的第一个查询 2.


示例输入 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 并给出 x=0。自从 0\notin S,添加 0 to S.
  • 第二个查询添加 3 to S.
  • 第三个查询的类型 2,我们有 S= \{ 0,3 \} 此时,所以 (0,3) 是唯一 (l,r) 这样 l,r\in S 和 0\leq l<r\leq N。我们有 f(0,3)=\frac{10}{3},所以打印 10 和 3 以空格分隔。
  • 第四个查询添加 2 to S.
  • 在第五次查询时,我们有 S=\{0,2,3\},以及对 (l,r) 是 (0,2), (0,3),和 (2,3)。最大 f(l,r) 是 f(2,3)=\frac{5}{1}。因此,打印 5 和 1 按此顺序。
  • 第六个查询添加 1 to S.
  • 我们有 3\in S 就在第七个查询之前,因此删除 3 来自 S.
  • 在第八次查询时,我们有 S=\{ 0,1,2\},以及最大 f(l,r) 满足条件的对是 f(1,2)=\frac{3}{1}。因此,打印 3 和 1 按此顺序。

示例输入 2

2 3
1 1
1 0
1 2
2

示例输出 2

1 1

请注意 P 和 Q 在每个类型的查询中 2 必须互质。也就是说,您不能打印 2 2 在此测试用例中。