题目内容

你在一家同城物流平台负责“运费估计引擎”。

平台记录了大量历史订单，每条订单有两个关键字段：

• $x$：运输距离（$\mathrm{km}$）
• $y$：成交运费（元）

为了给新订单快速报价，系统使用一元线性回归模型：

但市场价格持续波动，历史数据会不断新增。你需要实现一个在线学习模块，按操作实时维护模型并回答预测请求。

操作定义

• $ADD$ $x$ $y$：新增一条历史样本 $(x,y)$
• $QUERY$ $x_0$：基于当前所有样本拟合最小二乘直线，并输出在 $x_0$ 处的预测值

模型定义

在任意一次 $QUERY$ 时，设当前样本集合为 $(x_i,y_i)$，模型参数 $(a,b)$ 必须满足： 使平方误差和 $\sum(y_i-(a*x_i+b))^2$ 最小。 也就是说，$QUERY$ $x_0$ 输出的应是该最优模型在 $x_0$ 处的预测值。

对于一元线性回归，若当前样本数为 $n$，并记：

• $Sx=\sum x_i$
• $Sy=\sum y_i$
• $Sxx=\sum x_i^2$
• $Sxy=\sum x_i*y_i$

当最优解唯一时，可直接使用最小二乘法公式：

• $a=(n*Sxy-Sx*Sy)/(n*Sxx-Sx^2)$
• $b=(Sy-a*Sx)/n$

于是 $QUERY$ $x_0$ 的答案为：

• $yhat=a*x_0+b$

退化规则

• 若 $n=0$，$QUERY$ 输出 $0.000000$
• 若 $n\ge1$ 且最优解不唯一（等价于所有 $x$ 相同），为保证答案唯一，规定使用常数模型：
  • $a=0$
  • $b=$ 当前所有 $y$ 的平均值
  • $yhat=b$

数据范围

• $1 \le Q \le 200000$
• $-10^6 \le x,y,x0 \le 10^6$
• 保证中间统计量在 $64$ 位有符号整数范围内

输入描述

• 第 $1$ 行：整数 $Q$，表示操作总数
• 接下来 $Q$ 行，每行为以下两种之一：

ADD x y
QUERY x0

输出描述

• 对每个 $QUERY$ 输出一行预测值
• 结果必须输出为固定 $6$ 位小数

样例1

输入

8
ADD 10 35
ADD 20 55
QUERY 15
ADD 30 78
QUERY 25
ADD 25 69
QUERY 40
QUERY 5

输出

45.000000
66.750000
100.285714
23.685714

说明

• 前两条样本后，回归线为 $y=2x+15$，所以 $QUERY$ $15$ 输出 $45.000000$。
• 加入更多样本后，参数会变化，因此后续查询结果也会变化。

样例2

输入

7
ADD 12 30
ADD 12 36
QUERY 12
ADD 12 45
QUERY 100
QUERY -20
QUERY 0

输出

33.000000
37.000000
37.000000
37.000000

说明

• 所有样本的 $x$ 都等于 $12$，最小二乘解不唯一。
• 按退化规则使用常数模型，预测值恒为当前 $y$ 的平均值。