线段树写法,样例过了,0分,求调
  • 板块P1471 方差
  • 楼主Unknown__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/28 16:17
  • 上次更新2024/7/28 17:38:20
查看原帖
线段树写法,样例过了,0分,求调
357237
Unknown__楼主2024/7/28 16:17
#include <iostream>
#include <cmath>
#define ls (s << 1)
#define rs (s << 1 | 1)
using namespace std;
typedef double db;
const int N = 100010;
struct node{
    int l,r;
    db tag,aver,var,len;
}T[N << 2];
int n,m;
db A[N];
void pushup(node& A,node B,node C)
{
    db tot = B.len + C.len;
    A.aver = (B.len / tot) * B.aver + (C.len / tot) * C.aver;
    A.var = (B.len / tot) * (B.var + (A.aver - B.aver) * (A.aver - B.aver)) + (C.len / tot) * (C.var + (A.aver - C.aver) * (A.aver - C.aver));
}
void pushup(int s)
{
    pushup(T[s],T[ls],T[rs]);
}
void pushdown(int s)
{
    T[ls].aver += T[s].tag;
    T[rs].aver += T[s].tag;
    T[ls].tag += T[s].tag;
    T[rs].tag += T[s].tag;
    T[s].tag = 0.0;
}
void build(int s,int l,int r)
{
    T[s] = (node){l,r,0,0.0,0.0,db(r - l + 1)};
    if(l == r)
    {
        T[s].aver = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid);
    build(rs,mid + 1,r);
    pushup(s);
}
void modify(int s,int l,int r,db x)
{
    if(T[s].l == l && T[s].r == r)
    {
        T[s].aver += x;
        T[s].tag += x;
        return;
    }
    if(T[s].tag)pushdown(s);
    int mid = (T[s].l + T[s].r) >> 1;
    if(l > mid)modify(rs,l,r,x);
    else if(r <= mid)modify(ls,l,r,x);
    else modify(ls,l,mid,x),modify(rs,mid + 1,r,x);
    pushup(s);
}
node query(int s,int l,int r)
{
    if(T[s].l == l && T[s].r == r)return T[s];
    if(T[s].tag)pushdown(s);
    int mid = (T[s].l + T[s].r) >> 1;
    if(l > mid)return query(rs,l,r);
    else if(r <= mid)return query(ls,l,r);
    else
    {
        node ml = query(ls,l,mid),mr = query(rs,mid + 1,r);
        node ms;
        pushup(ms,ml,mr);
        return ms;
    }
}
int main()
{
    cin>>n>>m;
    int i;
    for(i = 1;i <= n;i++)cin>>A[i];
    build(1,1,n);
    while(m--)
    {
        int op;cin>>op;
        if(op == 1)
        {
            int l,r;cin>>l>>r;
            db x;cin>>x;
            modify(1,l,r,x);
        }
        else
        {
            int l,r;cin>>l>>r;
            node tmp = query(1,l,r);
            if(op == 2)printf("%.4lf\n",tmp.aver);
            else printf("%.4lf\n",tmp.var);
        }
    }
}

rt,我用的是s02=mm+n(s12+(s1‾−w‾)2)+nm+n(s22+(s2‾−w‾)2)s_0^2=\frac{m}{m+n}(s_1^2+(\overline{s_1}-\overline{w})^2)+\frac{n}{m+n}(s_2^2+(\overline{s_2}-\overline{w})^2) 这个公式,请问是精度爆了还是啥

2024/7/28 16:17
加载中...