我代码挺清晰的,求大神帮我!!全wa,样例过了。
  • 板块P1471 方差
  • 楼主Man_CCNU
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/6/24 09:08
  • 上次更新2023/10/27 22:43:26
查看原帖
我代码挺清晰的,求大神帮我!!全wa,样例过了。
524191
Man_CCNU楼主2022/6/24 09:08
#include<iostream>

using namespace std;

const int N = 1e5 + 10;
double a[N];
int n, m;
struct node {
    int l;
    int r;
    double sum;//区间和
    double psum; //平方和
    double fadd_;//标记
}b[N*4];

void update(int node)
{
    b[node].sum = b[node << 1].sum + b[node << 1 | 1].sum;
    b[node].psum = b[node << 1].psum + b[node << 1 | 1].psum;
}
void buit_tree(int node, int L, int R)
{
    b[node].l = L;
    b[node].r = R;
    if (L == R) {
        b[node].sum = a[L];
        b[node].psum = a[L] * a[L];
        return;
    }
    int mid = L + R >> 1;
    buit_tree(node << 1, L, mid);
    buit_tree(node << 1 | 1, mid + 1, R);
    update(node);

    return;
}
void down(int node)
{
    if (b[node].fadd_) {
        b[node << 1].fadd_ += b[node].fadd_;
        b[node << 1].psum += (2 * b[node].fadd_ * b[node<<1].sum + (b[node<<1].r - b[node << 1].l + 1) * b[node].fadd_ * b[node].fadd_);
        b[node << 1].sum += (b[node << 1].r - b[node << 1].l + 1) * b[node].fadd_;

        b[node << 1 | 1].fadd_ += b[node].fadd_;
        b[node << 1 | 1].psum += (2 * b[node].fadd_ * b[node << 1 | 1].sum + (b[node << 1 | 1].r - b[node << 1 | 1].l + 1) * b[node].fadd_ * b[node].fadd_);
        b[node << 1 | 1].sum += (b[node << 1 | 1].r - b[node << 1 | 1].l + 1) * b[node << 1].fadd_;

        b[node].fadd_ = 0;
    }

    return;
}
void add(int node, int l, int r, int x)
{
    int L = b[node].l;
    int R = b[node].r;
    if (l <= L && r >= R) {
        b[node].fadd_ += x;
        b[node].psum += (2 * x * b[node].sum + (b[node].r - b[node].l + 1) * x * x);
        b[node].sum += (b[node].r - b[node].l + 1) * x;
        return;
    }
    int mid = L + R >> 1;
    down(node);
    if (l <= mid) add(node << 1, l, r, x);
    if (r > mid) add(node << 1 | 1, l, r, x);
    update(node);

    return;
}
double qur(int node, int l, int r)//返回区间和
{
    int L = b[node].l;
    int R = b[node].r;
    if (l <= L && r >= R) {
        return b[node].sum;
    }
    int mid = L + R >> 1;
    down(node);
    
    double tem = 0;
    if (l <= mid) tem = tem + qur(node << 1, l, r);
    if (r > mid) tem = tem + qur(node << 1 | 1, l, r);

    return tem;
}
double qurpsum_(int node, int l, int r)//返回平方和
{
    int L = b[node].l;
    int R = b[node].r;
    if (l <= L && r >= R) {
        return b[node].psum;
    }
    int mid = L + R >> 1;
    down(node);
    double tem = 0;
    if (l <= mid) tem=tem+qurpsum_(node << 1, l, r);
    if (r > mid) tem=tem+qurpsum_(node << 1 | 1, l, r);

    return tem;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    buit_tree(1, 1, n);
    for (int i = 1; i <= m; i++) {
        double op, x, y, z;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            add(1, x, y, z);
        }
        else if (op == 2) {
            cin >> x >> y;
            double tem = qur(1, x, y);
            double tem3= tem / (y - x + 1);
            printf("%.4f\n", tem3);
        }
        else {
            cin >> x >> y;
            double tem = qur(1, x, y);//区间和
            double tem2 = qurpsum_(1, x, y);//平方和
            double tem_ = tem / (y - x + 1);//平均值
            double tem3=(tem2 - 2 * tem_ * tem + (y - x + 1) * tem_ * tem_) / (y - x + 1);
            printf("%.4f\n", tem3);
        }
    }

    return 0;
}
2022/6/24 09:08
加载中...