题目描述

Frank 对天文学非常感兴趣，他经常用望远镜看星星， 同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离、半径等等。

Frank 不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间 （比如亮度和半径） 是否存在某种关系。

现在 Frank 要分析参数 X X 与 Y Y 之间的关系。他有 n n 组观测数据，第 i i 组观测数据记录了 xi x_i 和 yi y_i 。他需耍进行以下几种操作：


  • 用直线拟合第 L L 组到第 R R 组观测数据。用 x¯ \bar x 表示这些观测数据中 x x 的平均数，用 y¯ \bar y 表示这些观测数据中 y y 的平均数，即

    x¯=1R−L+1∑i=LRxiy¯=1R−L+1∑i=LRyi \begin{aligned} \bar{x} &= \frac{1}{R - L + 1} \sum\limits_{i = L} ^ R x_i \\ \bar{y} &= \frac{1}{R - L + 1} \sum\limits_{i = L} ^ R y_i \end{aligned}

    如果直线方程是 y=ax+b y = ax + b ，那么 a a 、b b 应该这样计算：

    a=∑i=LR(xi−x¯)(yi−y¯)∑i=LR(xi−x¯)2b=y¯−ax¯ \begin{aligned} a &= \frac{\sum\limits_{i = L} ^ R (x_i - \bar{x})(y_i - \bar{y})}{\sum\limits_{i = L} ^ R (x_i - \bar{x}) ^ 2} \\ b &= \bar{y} - a \bar{x} \end{aligned}

    你需要帮助 Frank 计算 a a 。


  • Frank 发现测量第 L L 组到第 R R 组数据时有误差，对于每个 i i 满足 L≤i≤R L \leq i \leq R ，xi x_i 需要加上 S S ，yi y_i 需要加上 T T 。

  • Frank 发现第 L L 组到第 R R 组数据需要修改，对于每个 i i 满足 L≤i≤R L \leq i \leq R ，xi x_i 需要修改为 (S+i) (S + i) ，yi y_i 需要修改为 (T+i) (T + i) 。

题解

展开上式，发现只需维护区间 xi,yi,xiyi,xi2 x_i, y_i, x_iy_i, x_i^2 ，就可以回答上述问题。

对于修改操作 2 2 ，线段树区间修改随便搞，对于操作 3 3 由于给定的 S S 和 T T 可能为 0 0 ，所以需要一定奇技淫巧来标记该区间有无被复制。

线段树节点切勿忘记开 double。。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#define double long double
typedef long long ll;
const int MAX_N = 100000;
double x[MAX_N + 1], y[MAX_N + 1];
double sum[MAX_N + 1], sum2[MAX_N + 1];
inline void prepare() {
    sum[0] = 0, sum2[0] = 0;
    for (int i = 1; i <= MAX_N; i++) {
        sum[i] = sum[i - 1] + i;
        sum2[i] = sum2[i - 1] + (double)i * i;
    }
}
inline double calc(int l, int r) {
    return sum[r] - sum[l - 1];
}
inline double calc2(int l, int r) {
    return sum2[r] - sum2[l - 1];
}
struct Segt {
    int l, r;
    Segt *lc, *rc;
    double sx, sy, sxy, sxx;
    double tags, tagt;
    double cs, ct;
    bool changed;
    
    Segt(int l, int r, Segt *lc, Segt *rc) : l(l), r(r), lc(lc), rc(rc), 
        sx(lc->sx + rc->sx), sy(lc->sy + rc->sy),
            sxy(lc->sxy + rc->sxy), sxx(lc->sxx + rc->sxx), tags(0), tagt(0), 
                cs(0), ct(0), changed(false) {}
    Segt(int l, int r, Segt *lc, Segt *rc, double sx, double sy) : 
        l(l), r(r), lc(lc), rc(rc), sx(sx), sy(sy), sxy(sx * sy), sxx(sx * sx), 
            tags(0), tagt(0), cs(0), ct(0), changed(false) {}
    
    double querysx(int l, int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return sx;
        else return pushDown(), lc->querysx(l, r) + rc->querysx(l, r);
    }
    
    double querysy(int l, int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return sy;
        else return pushDown(), lc->querysy(l, r) + rc->querysy(l, r);
    }
    
    double querysxy(int l, int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return sxy;
        else return pushDown(), lc->querysxy(l, r) + rc->querysxy(l, r);
    }
    
    double querysxx(int l, int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return sxx;
        else return pushDown(), lc->querysxx(l, r) + rc->querysxx(l, r);
    }
    void validate() {
        double sx, sy, sxy, sxx;
        sx = this->sx;
        sy = this->sy;
        sxy = this->sxy;
        sxx = this->sxx;
        printf("Segt, sx : %lld, sy : %lld, sxy : %lld, sxx : %lld\n", (long long)sx, (long long)sy, (long long)sxy, (long long)sxx);
        sx = 0, sy = 0, sxy = 0, sxx = 0;
        for (int i = l; i <= r; i++) {
            sx += x[i];
            sy += y[i];
            sxy += (long long)x[i] * y[i];
            sxx += (long long)x[i] * x[i];
        }
        printf("Force, sx : %lld, sy : %lld, sxy : %lld, sxx : %lld\n", (long long)sx, (long long)sy, (long long)sxy, (long long)sxx);
    }
    
    void add(double s, double t) {
        sxy = sxy + sx * t + sy * s + s * t * (this->r - this->l + 1);
        sxx = sxx + s * s * (this->r - this->l + 1) + 2 * sx * s;
        sx += s * (this->r - this->l + 1);
        sy += t * (this->r - this->l + 1);
        tags += s;
        tagt += t;
//		validate();
    }
    void change(double s, double t) {
        double sump = calc(l, r), sumq = calc2(l, r);
        tags = 0, tagt = 0;
        int len = r - l + 1;
        sx = len * s + sump;
        sy = len * t + sump;
        sxy = len * s * t + sump * (s + t) + sumq;
        sxx = s * s * len + sumq + 2 * s * sump;
        cs = s, ct = t;
        changed = true;
//		validate();
    }
    
    void maintain() {
        sx = lc->sx + rc->sx;
        sy = lc->sy + rc->sy;
        sxy = lc->sxy + rc->sxy;
        sxx = lc->sxx + rc->sxx;
    }
    
    void pushDown() {
        if (changed) {
            lc->change(cs, ct);
            rc->change(cs, ct);
            
            changed = false;
        }
        if (tags != 0 || tagt != 0) {
            lc->add(tags, tagt);
            rc->add(tags, tagt);
            
            tags = 0, tagt = 0;
        }
    }
    
    void modify2(int l, int r, int s, int t) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) add(s, t);
        else pushDown(), lc->modify2(l, r, s, t), rc->modify2(l, r, s, t), maintain();
    }
    
    void change(int l, int r, int s, int t) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) change(s, t);
        else pushDown(), lc->change(l, r, s, t), rc->change(l, r, s, t), maintain();
    }
    
    static Segt *build(int l, int r) {
        if (l == r) {
            return new Segt(l, r, NULL, NULL, x[l], y[l]);
        } else {
            int mid = l + (r - l) / 2;
            return new Segt(l, r, build(l, mid), build(mid + 1, r));
        }
    }
} *segt;
inline void query(int l, int r) {
    double sxy = segt->querysxy(l, r);
    double sx = segt->querysx(l, r);
    double sy = segt->querysy(l, r);
    double sxx = segt->querysxx(l, r);
    double xa = (double)sx / (double)(r - l + 1);
    double ya = (double)sy / (double)(r - l + 1);
    double up = sxy - (double)sx * ya - (double)sy * xa + xa * ya * (double)(r - l + 1);
    double down = sxx + xa * xa * (double)(r - l + 1) - 2 * sx * xa;
    double ans = up / down;
    printf("%.10Lf\n", ans);
}
inline void modify2(int l, int r, double s, double t) {
    for (int i = l; i <= r; i++) {
        x[i] += s, y[i] += t;
    }
}
inline void change(int l, int r, double s, double t) {
    for (int i = l; i <= r; i++) {
        x[i] = s + i, y[i] = t + i;
    }
}
int main() {
    freopen("relative.in", "r", stdin);
    freopen("relative.out", "w", stdout);
    int n, m;
    prepare();
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%Lf", &x[i]);
    for (int i = 1; i <= n; i++) scanf("%Lf", &y[i]);
    
    segt = Segt::build(1, n);
    
    for (int i = 1; i <= m; i++) {
        int cmd;
        scanf("%d", &cmd);
        if (cmd == 1) {
            int l, r;
            scanf("%d %d", &l, &r);
            query(l, r);
        } else if (cmd == 2) {
            int l, r, s, t;
            scanf("%d %d %d %d", &l, &r, &s, &t);
//			modify2(l, r, s, t);
            segt->modify2(l, r, s, t);
        } else if (cmd == 3) {
            int l, r, s, t;
            scanf("%d %d %d %d", &l, &r, &s, &t);
//			change(l, r, s, t);
            segt->change(l, r, s, t);
        }
    }
    
    fclose(stdin), fclose(stdout);
    
    return 0;
}