#题面
#题目描述
Frank 对天文学非常感兴趣,他经常用望远镜看星星, 同时记录下它们的信息,比如亮度、颜色等等,进而估算出星星的距离、半径等等。
Frank 不仅喜欢观测,还喜欢分析观测到的数据。他经常分析两个参数之间 (比如亮度和半径) 是否存在某种关系。
现在 Frank 要分析参数 与 之间的关系。他有 组观测数据,第 组观测数据记录了 和 。他需耍进行以下几种操作:
-
用直线拟合第 组到第 组观测数据。用 表示这些观测数据中 的平均数,用 表示这些观测数据中 的平均数,即
如果直线方程是 ,那么 、 应该这样计算:
你需要帮助 Frank 计算 。
-
Frank 发现测量第 组到第 组数据时有误差,对于每个 满足 , 需要加上 , 需要加上 。
-
Frank 发现第 组到第 组数据需要修改,对于每个 满足 , 需要修改为 , 需要修改为 。
#输入格式
第一行两个数 、,表示观测数据组数和操作次数。
接下来一行 个数,第 个数是 。
接下来一行 个数,第 个数是 。
接下来 行,表示操作,格式见题目描述。
#输出格式
对于每个 1 操作,输出一行,表示直线斜率 。选手输出与标准输出的绝对误差或相对误差不超过 即为正确。
#样例输入输出
#样例输入 #1
3 5
1 2 3
1 2 3
1 1 3
2 2 3 -3 2
1 1 2
3 1 2 2 1
1 1 3
#样例输出 #1
1.0000000000
-1.5000000000
-0.6153846154
#数据范围与约定
- 对于 的数据,;
- 对于另外 的数据没有 3 操作,且 2 操作中 ;
- 对于另外 的数据没有 3 操作;
- 对于 的数据,,,,,1 操作中不会出现分母为 这类特殊情况。
#思路
首先需要转化 式。
这样只需要维护 、、、 即可,根据上式即可计算出斜率 ,免去了计算平均数的麻烦。
显然可以用线段树维护这些值。
-
对于操作 1,求出区间和后代入上式即可计算出答案。
-
对于操作 2,与线段树区间加类似,只不过处理懒标记时比较麻烦:
- ;
- ;
- ;
- 。
-
对于操作 3,可以先进行区间覆盖,再进行一次操作 2 将 添加到区间上。
在区间覆盖时,利用公式 可以快速计算出区间平方和。
本题数据会爆 long long
,请开 __int128
。
#代码
1 |
|