【题目描述】
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} sumlimits _{i=L} ^R x_i)
(overline{y}={1 over R-L+1} sumlimits _{i=L} ^R y_i)
如果直线方程是(y=ax+b)，那么(a)应当这样计算：
(a={sumlimits_{i=L} ^R (x_i-overline{x})(y_i-overline{y}) over sumlimits _{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={sumlimits_{i=L} ^R (x_i-overline{x})(y_i-overline{y}) over sumlimits _{i=L} ^R (x_i -overline{x})^2})
(={sumlimits_{i=L} ^R (x_i*y_i-overline{x}*y_i-x_i*overline{y}+overline{x}*overline{y}) over sumlimits _{i=L} ^R (x_i^2 -2*overline{x}*x_i+overline{x}^2)})
操作3可以看作先将(x_i,y_iin [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清零
代码
#include <bits/stdc++.h>
using namespace std;
typedef long double db;
int n, m;
db a[100005], b[100005];
int tp, l, r;
db s, t;
namespace Segtree{
struct tree{
int l, r;
db sumx, sumy, xy, xx;
int tagi;
db tagx, tagy;
} tr[400005];
#define lson ind<<1
#define rson ind<<1|1
inline void pushup(int ind) {
tr[ind].sumx = tr[lson].sumx + tr[rson].sumx;
tr[ind].sumy = tr[lson].sumy + tr[rson].sumy;
tr[ind].xx = tr[lson].xx + tr[rson].xx;
tr[ind].xy = tr[lson].xy + tr[rson].xy;
}
inline db getsum(int la, int ra) {
db l = la, r = ra;
return (r - l + 1) * (l + r) / 2;
}
inline db getsqr(int la, int ra) {
db l = la, r = ra;
return (r * (r + 1) * (2 * r + 1) - (l-1) * l * (2 * (l-1) + 1)) / 6;
}
inline void addxy(int ind, db vx, db vy) {
db len = (tr[ind].r - tr[ind].l + 1);
tr[ind].tagx += vx; tr[ind].tagy += vy;
tr[ind].xx += 2 * tr[ind].sumx * vx + vx * vx * len;
tr[ind].xy += len * vx * vy + tr[ind].sumx * vy + tr[ind].sumy * vx;
tr[ind].sumx += vx * len;
tr[ind].sumy += vy * len;
}
inline void addi(int ind) {
tr[ind].tagx = tr[ind].tagy = 0;
tr[ind].tagi = 1;
tr[ind].sumx = tr[ind].sumy = getsum(tr[ind].l, tr[ind].r);
tr[ind].xx = tr[ind].xy = getsqr(tr[ind].l, tr[ind].r);
}
inline void pushdown(int ind) {
if (tr[ind].tagi) {
tr[ind].tagi = 0;
addi(lson);
addi(rson);
}
if (tr[ind].tagx || tr[ind].tagy) {
int vx = tr[ind].tagx, vy = tr[ind].tagy;
tr[ind].tagx = tr[ind].tagy = 0;
addxy(lson, vx, vy);
addxy(rson, vx, vy);
}
}
void build(int ind, int l, int r) {
tr[ind].l = l, tr[ind].r = r;
tr[ind].tagi = tr[ind].tagx = tr[ind].tagy = 0;
if (l == r) {
tr[ind].sumx = a[l]; tr[ind].sumy = b[l];
tr[ind].xy = a[l] * b[l]; tr[ind].xx = a[l] * a[l];
return;
}
int mid = (l + r) >> 1;
build(ind<<1, l, mid); build(ind<<1|1, mid+1, r);
pushup(ind);
}
void update2(int ind, int x, int y, db vx, db vy) {
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
addxy(ind, vx, vy);
return;
}
int mid = (l + r) >> 1;
pushdown(ind);
if (x <= mid) update2(lson, x, y, vx, vy);
if (mid < y) update2(rson, x, y, vx, vy);
pushup(ind);
}
void update3(int ind, int x, int y) {
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
addi(ind);
return;
}
int mid = (l + r) >> 1;
pushdown(ind);
if (x <= mid) update3(lson, x, y);
if (mid < y) update3(rson, x, y);
pushup(ind);
}
inline tree merge(tree a, tree b) {
a.sumx += b.sumx;
a.sumy += b.sumy;
a.xx += b.xx;
a.xy += b.xy;
return a;
}
tree query(int ind, int x, int y) {
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
return tr[ind];
}
int mid = (l + r) >> 1;
pushdown(ind);
tree a, b;
a.sumx = a.sumy = a.xx = a.xy = 0;
b.sumx = b.sumy = b.xx = b.xy = 0;
if (x <= mid) a = query(lson, x, y);
if (mid < y) b = query(rson, x, y);
return merge(a, b);
}
}
using namespace Segtree;
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%Lf", &a[i]);
for (int i = 1; i <= n; i++) scanf("%Lf", &b[i]);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
scanf("%d", &tp);
if (tp == 1) {
scanf("%d %d", &l, &r);
tree ans = query(1, l, r);
db sumx = ans.sumx * 1.0, sumy = ans.sumy * 1.0, xx = ans.xx * 1.0, xy = ans.xy * 1.0;
db ax = sumx / (r - l + 1), ay = sumy / (r - l + 1);
db up = ax * ay * (r - l + 1) + xy - ay * sumx - ax * sumy;
db down = xx * 1.0 - 2.0 * ax * sumx + (r - l + 1) * ax * ax;
printf("%.10Lf
", up / down);
} else if (tp == 2) {
scanf("%d %d %Lf %Lf", &l, &r, &s, &t);
update2(1, l, r, s, t);
} else {
scanf("%d %d %Lf %Lf", &l, &r, &s, &t);
update3(1, l, r);
update2(1, l, r, s, t);
}
}
return 0;
}
如何一遍写对线段树？
单点修改(pos)
if (l == r) {
//进行修改
return;
}
int mid = (l + r) >> 1;
pushdown(ind);
if (pos <= mid) //向左儿子递归
else //向右儿子递归
//在最后要更新当前节点信息
区间修改([x,y])
if (x <= l && r <= y) {
//修改+打标记
return;
}
int mid = (l + r) >> 1;
pushdown(ind);
if (x <= mid) //向左儿子递归
if (mid < y) //向右儿子递归
//在最后要更新当前节点信息
pushdown记得清空父节点的tag
很模板的一个东西 查询的函数也差不多 但是最后不需要更新当前节点信息了