线段树求调
  • 板块P1471 方差
  • 楼主wwxxbb
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/5/5 20:41
  • 上次更新2024/5/6 11:13:57
查看原帖
线段树求调
1219662
wwxxbb楼主2024/5/5 20:41

rt,double 什么的都加了,还是 00 分。

#include <bits/stdc++.h>
// #define int long long
using namespace std;

const int N = 100010;

int n, m;
// double b[N];

#define ls u << 1
#define rs u << 1 | 1
struct node {
    int l, r;
    double s1, s2;
    double add;
}tr[N<<2];

void pushup(int u) {
    tr[u].s1 = tr[ls].s1 + tr[rs].s1;
    tr[u].s2 = tr[ls].s2 + tr[rs].s2;
}

void calc(int u, int add) {
    int l = tr[u].r - tr[u].l + 1;
    tr[u].s2 += 2 * add * tr[u].s1 + add * add * l;
    tr[u].s1 += l * add;
    tr[u].add += add;
}

void pushdown(int u) {
    if (!tr[u].add) return;
    calc(ls, tr[u].add), calc(rs, tr[u].add);
    tr[u].add = 0;
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        cin >> tr[u].s1;
        tr[u].s2 = tr[u].s1 * tr[u].s1;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, double v) {
    if (l <= tr[u].l && tr[u].r <= r){
        int L = tr[u].r - tr[u].l + 1;
        tr[u].s2 += 2 * v * tr[u].s1 + v * v * L;
        tr[u].s1 += v * L;
        tr[u].add += v;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(ls, l, r, v);
    if (r > mid) modify(rs, l, r, v);
    pushup(u);
}

double query1(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].s1;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    double res = 0;
    if (l <= mid) res += query1(ls, l, r);
    if (r > mid) res += query1(rs, l, r);
    return res;
}

double query2(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].s2;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    double res = 0;
    if (l <= mid) res += query2(ls, l, r);
    if (r > mid) res += query2(rs, l, r);
    return res;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    // for (int i = 1; i <= n; i++)
    //     cin >> b[i];
    build(1, 1, n);
    while (m--) {
        int c, x, y;
        double k;
        cin >> c >> x >> y;
        if (c == 1) {
            cin >> k;
            modify(1, x, y, k);
        } else if (c == 2) {
            int l = y - x + 1;
            cout << fixed << setprecision(4) << query1(1, x, y) / l << '\n'; 
        } else {
            int l = y - x + 1;
            double s1 = query1(1, x, y) / l;
            double s2 = query2(1, x, y) / l;
            cout << fixed << setprecision(4) << s2 - s1 * s1 << '\n';
        }
    }
    return 0;
}
2024/5/5 20:41
加载中...