相关分析[SDOI2017]
【题目描述】
Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。
Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。
现在Frank要分析参数$X$与$Y$之间的关系。他有$n$组观测数据，第$i$组观测数据记录了$x_i,y_i$。他需要以下几种操作：
1 L R
用直线拟合第$L$组到底$R$组观测数据。用$\overline{x}$表示这些观测数据中$x$的平均数，用$\overline{y}$表示这些观测数据中$y4的平均数，即
$\overline{x}={1 \over R-L+1} \sum\limits _{i=L} ^R x_i$
$\overline{y}={1 \over R-L+1} \sum\limits _{i=L} ^R y_i$
如果直线方程是$y=ax+b$，那么$a$应当这样计算：
$a={\sum\limits_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \sum\limits _{i=L} ^R (x_i -\overline{x})^2}$
你需要帮助Frank计算$a$。
2 L R S T
Frank发现测量数据第$L$组到底$R$组数据有误差，对每个$i$满足$L \leq i \leq R$，$x_i$需要加上$S$，$y_i$需要加上$T$。
3 L R S T
Frank发现第$L$组到第$R$组数据需要修改，对于每个$i$满足$L \leq i \leq R$，$x_i$需要修改为$(S+i)$，$y_i$需要修改为$(T+i)$。
【输入格式】
第一行两个数$n,m$，表示观测数据组数和操作次数。
接下来一行$n$个数，第$i$个数是$x_i$。
接下来一行$n$个数，第$i$个数是$y_i$。
接下来$m$行，表示操作，格式见题目描述。
【输出格式】
对于每个1操作，输出一行，表示直线斜率$a$。选手输出与标准输出的绝对误差或相对误差不超过$10^{-5}$即为正确。
题解
$a={\sum\limits_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \sum\limits _{i=L} ^R (x_i -\overline{x})^2}$
$={\sum\limits_{i=L} ^R (x_i*y_i-\overline{x}*y_i-x_i*\overline{y}+\overline{x}*\overline{y}) \over \sum\limits _{i=L} ^R (x_i^2 -2*\overline{x}*x_i+\overline{x}^2)}$
操作3可以看作先将$x_i,y_i\in [l,r]$全部置为$i$然后再进行一次2操作 显然是等价的
用线段树维护4个值：$\sum x, \sum y, \sum x*y, \sum x^2$
###细节：
这里用$sumx$表示$\sum x$，$sumy$表示$\sum y$，$xy$表示$\sum x*y$，$xx$表示$\sum x^2$。
操作2
将每个$x_i$加上$S$，每个$y_i$加上$T$
$sumx = sumx + (r-l+1) * S$
$sumy = sumy + (r-l+1) * T$
$xy = xy + (r-l+1)*S*T + sumx * T + sumy * S$
$xx = xx + (r-l+1)*S*S+2*sumx*S$
对于操作2 懒标记就正常地打 上面的4个式子都是可以通过暴力拆括号得到的 不推了
操作3
将每个$x_i,y_i$都置为$i$
$sumx = sumy = (r-l+1)*(l+1)/2$就是从$l$加到$r$。。。
$xx = xy = l^2+(l+1)^2+(l+2)^2+\dots +r^2$这个可以用平方和公式$O(1)$算 平方和公式是$1^2+2^2+\dots +n^2=\frac{n(n+1)(2n+1)}{6}$
注意 打操作3的tag时 因为这个是直接修改类的操作 要把操作2的tag清零
代码
1 |
|
如何一遍写对线段树？
单点修改$pos$
1 | if (l == r) { |
区间修改$[x,y]$
1 | if (x <= l && r <= y) { |
pushdown记得清空父节点的tag
很模板的一个东西 查询的函数也差不多 但是最后不需要更新当前节点信息了
