洛谷P1471 方差

题目背景

滚粗了的HansBug在收拾旧数学书，然而他发现了什么奇妙的东西。

题目描述

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示数列中实数的个数和操作的个数。

第二行包含N个实数，其中第i个实数表示数列的第i项。

接下来M行，每行为一条操作，格式为以下两种之一：

操作1：1 x y k ，表示将第x到第y项每项加上k，k为一实数。

操作2：2 x y ，表示求出第x到第y项这一子数列的平均数。

操作3：3 x y ，表示求出第x到第y项这一子数列的方差。

输出格式：

输出包含若干行，每行为一个实数，即依次为每一次操作2或操作3所得的结果（所有结果四舍五入保留4位小数）。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

3.0000
2.0000
0.8000

本题要求维护方差和平均数，并且支持区间加。

平均数x0是比较简单的，维护区间和就行了，那么方差呢？当然是维护区间数的平方和啦！我们把方差的(x - x0)^2拆开，成为x^2 - x * x0 * 2 + x0 ^ 2这样我们只要有平均数和平方和就可以维护方差啦！

#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
double data[maxn];

namespace Segtree {
    struct node {
        int l, r;
        double sqsum, sum, addt;
    }tree[maxn << 2];
    
    void push_up(int rt) {
        tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
        tree[rt].sqsum = tree[rt << 1].sqsum + tree[rt << 1 | 1].sqsum;
    }
    
    void push_down(int rt) {
        if(tree[rt].addt != 0) {
            int tl = tree[rt].l;
            int tr = tree[rt].r;
            double addt = tree[rt].addt;
            int mid = tl + tr >> 1;
            tree[rt << 1].addt += addt;
            tree[rt << 1 | 1].addt += addt;
            tree[rt << 1].sqsum += 2 * tree[rt << 1].sum * addt + addt * addt * (mid - tl + 1);
            tree[rt << 1 | 1].sqsum += 2 * tree[rt << 1 | 1].sum * addt + addt * addt * (tr - mid);
            tree[rt << 1].sum += addt * (mid - tl + 1);
            tree[rt << 1 | 1].sum += addt * (tr - mid);
            tree[rt].addt = 0;
        }
    }
    
    void build(int l, int r, int rt) {
        tree[rt].l = l, tree[rt].r = r;
        if(l == r) {
            tree[rt].sum = data[l];
            tree[rt].sqsum = data[l] * data[l];
            return ;
        }
        int mid = l + r >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        push_up(rt);
    }
    
    void add(int l, int r, double dt, int rt) {
        int tl = tree[rt].l;
        int tr = tree[rt].r;
        if(tl == l && tr == r) {
            tree[rt].addt += dt;
            tree[rt].sqsum += tree[rt].sum * dt * 2 + dt * dt * (tr - tl + 1);
            tree[rt].sum += dt * (tr - tl + 1);
            return;
        }
        push_down(rt);
        int mid = tl + tr >> 1;
        if(r <= mid) add(l, r, dt, rt << 1);
        else if(l > mid) add(l, r, dt, rt << 1 | 1);
        else add(l, mid, dt, rt << 1), add(mid + 1, r, dt, rt << 1 | 1);
        push_up(rt);
    }
    
    double q_sqsum(int l, int r, int rt) {
        int tl = tree[rt].l, tr = tree[rt].r;
        if(l == tl && r == tr)
            return tree[rt].sqsum;
        int mid = tl + tr >> 1;
        push_down(rt);
        if(r <= mid) return q_sqsum(l, r, rt << 1);
        else if(l > mid) return q_sqsum(l, r, rt << 1 | 1);
        else return q_sqsum(l, mid, rt << 1) + q_sqsum(mid + 1, r, rt << 1 | 1);
    }
    
    double q_sum(int l, int r, int rt) {
        int tl = tree[rt].l, tr = tree[rt].r;
        if(l == tl && r == tr)
            return tree[rt].sum;
        int mid = tl + tr >> 1;
        push_down(rt);
        if(r <= mid) return q_sum(l, r, rt << 1);
        else if(l > mid) return q_sum(l, r, rt << 1 | 1);
        else return q_sum(l, mid, rt << 1) + q_sum(mid + 1, r, rt << 1 | 1);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= n; ++i) {
        scanf("%lf", &data[i]);
    }
    Segtree::build(1, n, 1);
    int op, l, r;
    double num;
    while(m--) {
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) 
            scanf("%lf", &num), Segtree::add(l, r, num, 1);
        if(op == 2) printf("%.4lf\n", Segtree::q_sum(l, r, 1) / (r - l + 1));
        if(op == 3) {
            double sum = Segtree::q_sum(l, r, 1);
            double avr = sum / (r - l + 1);
            double sqr = Segtree::q_sqsum(l, r, 1);
            double ans = sqr / (r - l + 1) - sum * 2 * avr / (r - l + 1) + avr * avr;
            printf("%.4lf\n", ans);
        }
    }
    return 0;
}

Rockdu's Blog