10分求调
  • 板块P1471 方差
  • 楼主huihuihuihui
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/14 16:11
  • 上次更新2023/11/2 13:53:46
查看原帖
10分求调
874087
huihuihuihui楼主2023/10/14 16:11
#include<bits/stdc++.h>
#define ls x << 1
#define rs x << 1 | 1
using namespace std;
const int N = 1e5 + 10;
int n , m;
double w[N];
struct {
    int l , r;
    double  sum;
    double powsum;
    double lazy;
}tr[N << 2];
void pushup(int x){
    tr[x].sum = tr[ls].sum + tr[rs].sum;
    tr[x].powsum= tr[ls].powsum + tr[rs].powsum;
}
void build(int x , int l , int r){
    if(l == r){
        tr[x] = {l,r ,1.0 *  w[l] , 1.0 *  w[l] * w[l]};
        return;
    }
    tr[x] = {l ,r};
    int mid = l + r >> 1;
    build(ls, l , mid);
    build(rs, mid + 1 ,r);
    pushup(x);
}
void pushdown(int x){
    if(tr[x].lazy)
    {
        tr[ls].powsum += tr[ls].sum * tr[x].lazy * 2 + (tr[ls].r - tr[ls].l + 1) * tr[x].lazy * tr[x].lazy;
        tr[ls].sum += (tr[ls].r - tr[ls].l + 1) * tr[x].lazy;
        tr[rs].powsum += tr[rs].sum * tr[x].lazy * 2 + (tr[rs].r - tr[rs].l + 1) * tr[x].lazy * tr[x].lazy;
        tr[rs].sum += (tr[rs].r - tr[rs].l + 1) * tr[x].lazy;
        tr[ls].lazy += tr[x].lazy;
        tr[rs].lazy += tr[x].lazy;
        tr[x].lazy = 0;
    }
}
void modify(int x , int l , int r , long double k){
    if(l <= tr[x].l && r >= tr[x].r){
        tr[x].lazy = k;
        tr[x].powsum += 1.0 * 2 * k * tr[x].sum + 1.0 * (tr[x].r - tr[x].l + 1) * k * k;
        tr[x].sum += 1.0 * (tr[x].r - tr[x].l + 1) * k;
        return;
    }
    pushdown(x);
    int mid = tr[x].l + tr[x].r >> 1;
    if(l <= mid) modify(ls , l , r , k);
    if(r > mid) modify(rs,l,r,k);
    pushup(x);
}
long double querysum(int x , int l , int r){
    if(l <= tr[x].l &&  r >= tr[x].r) return tr[x].sum;
    pushdown(x);
    long double v = 0;
    int mid = tr[x].l + tr[x].r >> 1;
    if(l <= mid) v += querysum(ls,l,r);
    if(r > mid) v += querysum(rs,l,r);
    return v;
}
double querypowsum(int x , int l , int r){
    if(l <= tr[x].l &&  r >= tr[x].r) return tr[x].powsum;
    pushdown(x);
    double v = 0;
    int mid = tr[x].l + tr[x].r >> 1;
    if(l <= mid) v += querypowsum(ls,l,r);
    if(r > mid) v += querypowsum(rs,l,r);
    return v;
}

int main(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) cin >> w[i];
    build(1,1,n);

    // for(int i = 1 ; i <= 9 ; i ++) {
    //     cout << i << " " << tr[i].l << " " << tr[i].r << " " << tr[i].sum << " " << tr[i].powsum << "\n";
    // }

    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int l , r ;
            long double k;
            cin >> l >> r >> k;
            modify(1,l,r,k);
        }

        if(op == 2){
            int l ,r;
            cin >> l >> r;
            //cout << querysum(1,l,r) << "\n";
            cout << fixed <<setprecision(4) << querysum(1,l,r) / (1.0 * (r - l + 1)) << "\n";
        }
        if(op == 3){
            int l ,r;
            cin >> l >> r;
            long double avg = querysum(1,l,r) / (1.0 * (r -l + 1));
            //cout << avg << " ";
            long double d = querypowsum(1,l,r);
            //cout << d << " ";
            cout <<  fixed << setprecision(4) <<  -1.0 * avg * avg  + d / (1.0 * (r - l + 1) )<< "\n";

        }

    }
}
2023/10/14 16:11
加载中...