AT_past202309_l 平均クエリ

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$，并有一个初始为空的集合 $S$。 定义 $f(L,R)$ 为：$f(L,R) = \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L}$，其中 $0\leq L

输入通过标准输入给出，格式如下： > $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$

输出 $k$ 行，其中 $k$ 为类型 $2$ 的操作个数。 对于第 $i$ 个类型 $2$ 操作，输出一行结果：用空格分隔的 $P\ Q$，其中答案为互质正整数 $\frac{P}{Q}$。

### 样例解释 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$，将 $0$ 加入 $S$。 - 第 2 次操作将 $3$ 加入 $S$。 - 第 3 次操作为类型 $2$，此时 $S= \{ 0,3 \}$，唯一的 $(l,r)$ 为 $(0,3)$，$f(0,3)=\frac{10}{3}$，输出 $10\ 3$。 - 第 4 次操作将 $2$ 加入 $S$。 - 第 5 次操作时，$S=\{0,2,3\}$，满足条件的 $(l,r)$ 有 $(0,2)$、$(0,3)$、$(2,3)$，最大 $f(l,r)$ 为 $f(2,3)=\frac{5}{1}$，输出 $5\ 1$。 - 第 6 次操作将 $1$ 加入 $S$。 - 第 7 次操作前 $3\in S$，将 $3$ 从 $S$ 移除。 - 第 8 次操作时，$S=\{ 0,1,2\}$，最大 $f(l,r)$ 为 $f(1,2)=\frac{3}{1}$，输出 $3\ 1$。 ### 样例解释 2 请注意，每次类型 $2$ 操作的 $P$ 和 $Q$ 必须是互质的。例如本测试点不能输出 `2 2`。 ### 数据范围 - $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)$。 由 ChatGPT 5 翻译