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<R\leq N$。

共要按顺序处理 $Q$ 个操作。每个操作有以下两种类型之一：

• 类型 $1$ ：给定一个整数 $x$，满足 $0\leq x\leq N$。如果 $x\notin S$，则将 $x$ 加入 $S$；否则，从 $S$ 中移除 $x$。
• 类型 $2$ ：设 $X$ 为所有满足 $l,r\in S$ 且 $0\leq l<r\leq N$ 的整数对 $(l,r)$ 中 $f(l,r)$ 的最大值。此时，将 $X$ 表示为互质的正整数 $\frac{P}{Q}$，输出 $P$ 和 $Q$，用空格分隔。保证每次处理类型 $2$ 操作时，至少存在一个 $(l,r)$ 满足上述条件。

输入通过标准输入给出，格式如下：

$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 翻译