问题陈述
给你一个长度序列 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 在此测试用例中。