#P4821. [Sdoi2017]相关分析

    ID: 3934 传统题 1000ms 128MiB 尝试: 848 已通过: 287 难度: 6 上传者: 标签>难度分类提高数据结构懒标记线段树标记复合线性代数与代数等差数列求和CF2100

[Sdoi2017]相关分析

题目描述

Frank 喜欢用望远镜观测星星,记录亮度、颜色等信息,并据此估算距离和半径。他还想分析不同参数之间的关系。

现在有 nn 组观测数据,第 ii 组为 (xi,yi)(x_i,y_i)。处理以下三种操作。

1 L R

用直线 y=ax+by=ax+b 拟合第 LL 到第 RR 组的观测数据。区间内两组数的平均值分别为

$$\overline{x}=\frac{\sum_{i=L}^{R}x_i}{R-L+1}, \qquad \overline{y}=\frac{\sum_{i=L}^{R}y_i}{R-L+1}.$$

求拟合直线的斜率

$$a=\frac{\sum_{i=L}^{R}(x_i-\overline{x})(y_i-\overline{y})} {\sum_{i=L}^{R}(x_i-\overline{x})^2}.$$

2 L R S T

修正观测误差。对所有 L≤i≤RL\le i\le R,将 xix_i 加上 SS,将 yiy_i 加上 TT。

3 L R S T

替换观测数据。对所有 L≤i≤RL\le i\le R,令 xi=S+ix_i=S+i、yi=T+iy_i=T+i。

输入格式

从标准输入读入数据。第一行两个整数 n,mn,m,表示观测组数和操作次数。

第二行 nn 个整数,依次为 x1,…,xnx_1,\ldots,x_n。第三行 nn 个整数,依次为 y1,…,yny_1,\ldots,y_n。

接下来 mm 行,每行一个操作,格式见题目描述,且 1≤L≤R≤n1\le L\le R\le n。

输出格式

向标准输出依次为每次类型 11 的询问写出一行一个实数,表示斜率 aa。答案的绝对误差或相对误差不超过 10−510^{-5} 即视为正确。

样例

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.0000000000
-1.5000000000
-0.6153846154

数据范围与约定

  • 对于 20%20\% 的数据,1≤n,m≤10001\le n,m\le 1000。
  • 另有 20%20\% 的数据,没有类型 33 的操作,且类型 22 中 S=0S=0。
  • 另有 30%30\% 的数据,没有类型 33 的操作。
  • 对于 100%100\% 的数据,1≤n,m≤1051\le n,m\le 10^5,所有初始的 ∣xi∣,∣yi∣|x_i|,|y_i| 和操作参数 ∣S∣,∣T∣|S|,|T| 均不超过 10510^5。

保证每次类型 11 的询问中,斜率公式的分母均非零。