题解 P1471 【方差】

高天 · 2020-02-25 19:27:27 · 题解

#include<iostream>
#include<iomanip>
using namespace std;
const int N = 100005, INF = 0x7fffffff;
double a[N], sum[4*N], sum2[4*N];
double tag[4*N];

void pushup(int k) {
    sum[k] = sum[k * 2] + sum[k * 2 + 1]; //区间和
    sum2[k] = sum2[k * 2] + sum2[k * 2 + 1]; //区间平方和
    return ;
}

void build(int k, int lt, int rt) { //第k个结点， lt rt为要询问的区间范围
    if(lt == rt) {
        sum[k] = a[lt]; //a为原始数组，sum[k]为第k个结点的区间和
        sum2[k] = a[lt] * a[lt]; //平方
        return ;
    }
    int mid = lt + (rt - lt) / 2; // mid = (lt + rt) >> 1
    build(k * 2, lt, mid);
    build(k * 2 + 1, mid + 1, rt);
    pushup(k);
    return ;
}

void Add(int k, int lt, int rt, double val) { //打懒标记
    tag[k] += val; //标记K结点对应的区间要加的值
    sum2[k] += 2 * val * sum[k] + val * val * (rt - lt + 1); //因为平方和要用到 区间和， 所以要先更新！
    sum[k] += (rt - lt + 1) * val;
    return ;
}

void pushdown(int k, int lt, int rt) {
    if(tag[k] == 0)
        return ;
    int mid = lt + (rt - lt) / 2;
    Add(k*2, lt, mid, tag[k]);
    Add(k*2+1, mid+1, rt, tag[k]);
    tag[k] = 0; //将标记传给子节点后，父节点的标记要清零，否则会加重复
    return ;
}

//在qx, qy区间每个数加上val
void modify(int k, int lt, int rt, int qx, int qy, double val) {
    if(lt > qy || rt < qx)
        return ;
    else if(lt >= qx && rt <= qy) {
        Add(k, lt, rt, val);
        return ;
    }
    int mid = lt + (rt - lt) / 2;
    pushdown(k, lt, rt);
    modify(k * 2, lt, mid, qx, qy, val);
    modify(k * 2 + 1 , mid + 1, rt, qx, qy, val);
    pushup(k);
    return ;
}

double query(int k, int lt, int rt, int qx, int qy) {
    if(lt > qy || rt < qx)
        return 0;
    else if(lt >= qx && rt <= qy)
        return sum[k];
    int mid = lt + (rt - lt) / 2;
    pushdown(k, lt, rt); //询问时才下传标记，因为需要知道子区间要加的值
    return query(k * 2, lt, mid, qx, qy) + query(k * 2 + 1, mid + 1, rt, qx, qy);
}

double query2(int k, int lt, int rt, int qx, int qy) {
    if(lt > qy || rt < qx)
        return 0;
    else if(lt >= qx && rt <= qy)
        return sum2[k];
    int mid = lt + (rt - lt) / 2;
    pushdown(k, lt, rt); //询问时才下传标记，因为需要知道子区间要加的值
    return query2(k * 2, lt, mid, qx, qy) + query2(k * 2 + 1, mid + 1, rt, qx, qy);
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n); //建树
    for(int i = 1; i <= m; i++) {
        int option, x, y;
        double v;
        cin >> option;
        if(option == 1) {
            cin >> x >> y >> v;
            modify(1, 1, n, x, y, v);
        } else if(option == 2) {
            cin >> x >> y;
            cout << fixed << setprecision(4) << query(1, 1, n, x, y) / (y-x+1) << "\n";
        } else {
            cin >> x >> y;
            double avg = query(1, 1, n, x, y) / (y-x+1);
            cout << fixed << setprecision(4) << -avg * avg + query2(1, 1, n, x, y) / (y-x+1) << "\n";
        }
    }
    return 0;
}