P3707 [SDOI2017] 相关分析 题解
- Luogu P3707
- LibreOJ L2005
- AcWing 2585
- BZOJ #4821
这道题需要我们维护一大坨东西。
准备与计算答案
首先我们把线性回归方程的公式拆一下：
（这里将 $\sum_{i=l}^r$ 省略为 $\sum$）
$$
\begin{align}
\hat{a} &= \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x}^2)} \\
&= \frac{\sum (x_i y_i - y_i \bar{x} - x_i \bar{y} + \bar{x} \bar{y})}{\sum (x_i^2 - 2x_i \bar{x} + \bar{x}^2)} \\
&= \frac{\sum x_i y_i - \bar{x} \sum y_i - \bar{y} \sum x_i + (r-l+1) \bar{x} \bar{y}}{\sum x_i^2 - 2\bar{x} \sum x_i + (r-l+1)\bar{x}^2} \\
&= \frac{\sum x_i y_i - \frac{\sum x_i \sum y_i}{r-l+1} - \frac{\sum y_i \sum x_i}{r-l+1} + (r-l+1) \frac{\sum x_i \sum y_i}{(r-l+1)^2}}{\sum x_i^2 - 2\frac{\sum x_i \sum x_i}{(r-l+1)} + (r-l+1) (\frac{\sum x_i}{r-l+1})^2} \\
&= \frac{\sum x_i y_i - \frac{\sum x_i \sum y_i}{r-l+1}}{\sum x_i^2 - \frac{\sum x_i \sum x_i}{r-l+1}}
\end{align}
$$
最终我们需要维护的就是 $\sum x_i$，$\sum x_i^2$，$\sum y_i$ 和 $\sum x_i y_i$。
我们计算时的公式就是 $\hat{a} = \frac{\sum x_i y_i - \frac{\sum x_i \sum y_i}{r-l+1}}{\sum x_i^2 - \frac{(\sum x_i)^2}{r-l+1}}$。
区间加
我们考虑每一个量是怎么变化的：
$\sum (x_i+s)^2 = \sum (x_i^2 + 2sx_i + s^2) = \sum x_i^2 + 2s\sum x_i + (r-l+1)s^2$
$\sum (x_i+s)(y_i+t) = \sum (x_iy_i + sy_i + ts_i + st) = \sum x_iy_i + s\sum y_i + t\sum x_i + (r-l+1)st$
$\sum (x_i+s) = \sum x_i + (r-l+1)s$
$\sum (y_i+t) = \sum y_i + (r-l+1)t$
注意我们这里在维护前面两个二次的东西的时候需要我们一次的这两个量，所以我们需要注意维护的顺序。
区间修改
前置芝士
$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$
转化
我们考虑将每一个点的值拆分成 $(i,i)$ 和 $(s,t)$ 两部分，而后者可以用区间加来完成。
这个 $i$ 就是当前点的编号。一开始我想的是每一个修改区间的 $i$ 从 $1$ 开始，傻乎乎地传了一个 $i$ 下去，然后wa了一堆……
对于一个完全被修改的区间 $[l,r]$，我们的四个量的新值如下：
$\sum x_i^2 = \sum i^2 = \sum_{i=1}^r i^2 - \sum_{i=1}^{l-1} = \frac{r(r+1)(2r+1)}{6} - \frac{(l-1)l(2l-1)}{6}$
$\sum x_iy_i = \sum i^2 = \frac{r(r+1)(2r+1)}{6} - \frac{(l-1)l(2l-1)}{6}$
$\sum x_i = \sum i = \frac{(r-l+1)(l+r)}{2}$
$\sum y_i = \sum i = \frac{(r-l+1)(l+r)}{2}$
然后需要清空懒标记，并打一个清空懒标记的标记。
然后就是区间加了。
注意事项
注意懒标记的维护顺序。
代码如下：
1 |
|