【题解】[Sdoi2017] 相关分析 傻×线段树 BZOJ – 4821

题目戳这里

首先你要知道这是要你维护回归直线的斜率

$a = \frac {\sum _ {i = 1} ^ {n} x _ i \times y _ i – n \bar x \bar y} {\sum _ {i = 1} ^ {n} x _ i ^ 2 – n \bar x ^2}$

然后你只要维护 $x,y,xy,x ^ 2$的值就行啦

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m;

double X[NS], Y[NS];

struct N
{
    int l, r;
    double x, y, xx, xy, s, t, len;
    bool tag, cov;
} e[NS << 2];

void pup(int a)
{
    int l = LS(a), r = RS(a);
    e[a].x = e[l].x + e[r].x;
    e[a].y = e[l].y + e[r].y;
    e[a].xx = e[l].xx + e[r].xx;
    e[a].xy = e[l].xy + e[r].xy;
}

void pdown(int a)
{
    int l = LS(a), r = RS(a);
    if (e[a].cov)
    {
        e[l].x = e[l].y = e[l].len * (e[l].l + e[l].r) * 0.5;
        e[r].x = e[r].y = e[r].len * (e[r].l + e[r].r) * 0.5;
        e[l].xx = ((double)e[l].r * (e[l].r + 1) * (2 * e[l].r + 1)) / 6;
        e[l].xx -= ((double)(e[l].l - 1) * e[l].l * (2 * e[l].l - 1)) / 6;
        e[r].xx = ((double)e[r].r * (e[r].r + 1) * (2 * e[r].r + 1)) / 6;
        e[r].xx -= ((double)(e[r].l - 1) * e[r].l * (2 * e[r].l - 1)) / 6;
        e[l].xy = e[l].xx, e[r].xy = e[r].xx;
        e[l].s = e[l].t = e[r].s = e[r].t = e[l].tag = e[r].tag = 0;
        e[l].cov = e[r].cov = 1, e[a].cov = 0;
    }
    if (e[a].tag)
    {
        double s, t;
        s = e[a].s, t = e[a].t, e[a].s = e[a].t = e[a].tag = 0;
        e[l].xx += s * s * e[l].len + s * e[l].x * 2;
        e[l].xy += s * t * e[l].len + e[l].x * t + e[l].y * s;
        e[l].x += s * e[l].len, e[l].y += t * e[l].len;
        e[l].s += s, e[l].t += t, e[l].tag = 1;
        e[r].xx += s * s * e[r].len + s * e[r].x * 2;
        e[r].xy += s * t * e[r].len + e[r].x * t + e[r].y * s;
        e[r].x += s * e[r].len, e[r].y += t * e[r].len;
        e[r].s += s, e[r].t += t, e[r].tag = 1;
    }
}

void Build(int l, int r, int a)
{
    e[a].l = l, e[a].r = r, e[a].len = r - l + 1;
    if (l == r)
    {
        e[a].x = X[l], e[a].y = Y[l];
        e[a].xx = X[l] * X[l], e[a].xy = X[l] * Y[l];
        return;
    }
    int mid = (l + r) >> 1;
    Build(l, mid, LS(a)), Build(mid + 1, r, RS(a)), pup(a);
}

double sxy, sx, sy, sxx;

void Query(int l, int r, int a)
{
    if (l <= e[a].l && e[a].r <= r)
        {sxy += e[a].xy, sx += e[a].x, sy += e[a].y, sxx += e[a].xx; return;}
    pdown(a);
    if (l <= e[LS(a)].r) Query(l, r, LS(a));
    if (r >= e[RS(a)].l) Query(l, r, RS(a));
}

inline double Cal_Ans(int len)
{
    return (sxy - sx / len * sy) / (sxx - sx / len * sx);
}

void Add(int l, int r, double s, int t, int a)
{
    if (l <= e[a].l && e[a].r <= r)
    {
        e[a].xx += s * s * e[a].len + s * e[a].x * 2;
        e[a].xy += s * t * e[a].len + e[a].x * t + e[a].y * s;
        e[a].x += s * e[a].len, e[a].y += t * e[a].len;
        e[a].s += s, e[a].t += t, e[a].tag = 1;
        return;
    }
    pdown(a);
    if (l <= e[LS(a)].r) Add(l, r, s, t, LS(a));
    if (r >= e[RS(a)].l) Add(l, r, s, t, RS(a));
    pup(a);
}

void Cov(int l, int r, int a)
{
    if (l <= e[a].l && e[a].r <= r)
    {
        e[a].x = e[a].len * (e[a].l + e[a].r) * 0.5;
        e[a].y = e[a].x;
        e[a].xx = ((double)e[a].r * (e[a].r + 1) * (2 * e[a].r + 1)) / 6;
        e[a].xx -= ((double)(e[a].l - 1) * e[a].l * (2 * e[a].l - 1)) / 6;
        e[a].xy = e[a].xx, e[a].s = e[a].t = e[a].tag = 0, e[a].cov = 1;
        return;
    }
    pdown(a);
    if (l <= e[LS(a)].r) Cov(l, r, LS(a));
    if (r >= e[RS(a)].l) Cov(l, r, RS(a));
    pup(a);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1) IN(X[i]);
    for (int i = 1; i <= n; i += 1) IN(Y[i]);
    Build(1, n, 1);
    while (m--)
    {
        int o, l, r; double s, t;
        IN(o), IN(l), IN(r);
        if (o == 1)
        {
            sxy = sx = sy = sxx = 0, Query(l, r, 1);
            printf("%.10f\n", Cal_Ans(r - l + 1));
        }
        else if (IN(s), IN(t), o == 2) Add(l, r, s, t, 1);
        else Cov(l, r, 1), Add(l, r, s, t, 1);
    }
    return 0;
}