线段树40分求助,WA #1 #2 #3 #4 #9 #10
  • 板块P1471 方差
  • 楼主MlKE
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/11/22 09:36
  • 上次更新2023/11/3 23:46:06
查看原帖
线段树40分求助,WA #1 #2 #3 #4 #9 #10
492732
MlKE楼主2021/11/22 09:36

rt

#include <bits/stdc++.h>
#define len double(t[p].r - t[p].l + 1)
#define db double
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
template <class T>
inline void read(T &x)
{
    x = 0;
    T w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    x = x * w;
}
const int N = 1e5 + 10;
int n, m;
db a[N];
struct SegmentTree
{
    int l, r;
    // fc [l,r]中所有数的平方的和
    db sum, fc, add;
} t[N << 2];
void pushup(int p)
{
    t[p].sum = t[ls].sum + t[rs].sum;
    t[p].fc = t[ls].fc + t[rs].fc;
}
void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        t[p].sum = a[l];
        t[p].fc = a[l] * a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}
void pushdown(int p)
{
    if (!t[p].add)
        return;
    db lenr = (t[rs].r - t[rs].l + 1), lenl = (t[ls].r - t[ls].l + 1);
    // fc
    t[ls].fc += t[p].add * (lenl * t[p].add + 2 * t[ls].sum);
    t[rs].fc += t[p].add * (lenr * t[p].add + 2 * t[rs].sum);
    // sum
    t[ls].sum += lenl * t[p].add;
    t[rs].sum += lenr * t[p].add;
    //add
    t[ls].add += t[p].add, t[rs].add += t[p].add;
    t[p].add = 0;
}
void modify(int p, int l, int r, db k)
{
    if (t[p].l >= l && t[p].r <= r)
    {
        t[p].fc += k * (len * k + 2 * t[p].sum);
        t[p].sum += len * k, t[p].add += k;
        return;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid)
        modify(ls, l, r, k);
    if (r > mid)
        modify(rs, l, r, k);
    pushup(p);
}
db query_sum(int p, int l, int r)
{
    if (t[p].l >= l && t[p].r <= r)
        return t[p].sum;
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    db val = 0;
    if (l <= mid)
        val += query_sum(ls, l, r);
    if (r > mid)
        val += query_sum(rs, l, r);
    return val;
}
db query_fc(int p, int l, int r)
{
    if (t[p].l >= l && t[p].r <= r)
    {
        db xi = t[p].fc - (t[p].sum * t[p].sum) / len;
        return xi;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    db val = 0;
    if (l <= mid)
        val += query_fc(ls, l, r);
    if (r > mid)
        val += query_fc(rs, l, r);
    return val;
}
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &a[i]);
    build(1, 1, n);
    int op, x, y;
    db k;
    for (int i = 1; i <= m; i++)
    {
        read(op);
        read(x);
        read(y);
        if (op == 1)
        {
            scanf("%lf", &k);
            modify(1, x, y, k);
        }
        else if (op == 2)
            printf("%.4lf\n", double(query_sum(1, x, y)) / double(y - x + 1));
        else if (op == 3)
            printf("%.4lf\n", double(query_fc(1, x, y)) / double(y - x + 1));
    }
    return 0;
}
2021/11/22 09:36
加载中...