线段树40pts 似乎是精度问题
  • 板块P1471 方差
  • 楼主__mcx_
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/21 20:20
  • 上次更新2023/10/23 20:54:55
查看原帖
线段树40pts 似乎是精度问题
308439
__mcx_楼主2023/3/21 20:20

wa的点均输出负数,int类型的乘了1.0想强制转换不过好像不行,求大佬解答

#include<bits/stdc++.h>
#define ll long long
#define dl long double
#define lp (p<<1)
#define rp (p<<1|1)
#define mid ((l+r)>>1)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=b;i>=a;i--)
#define up t[p].sum = t[lp].sum+t[rp].sum,t[p].v = t[lp].v+t[rp].v;
using namespace std;
const int nn = 1e5+10;
struct tree
{
    dl v,sum;//v = sum^2 sum = al to ar 
    dl add;   
}t[nn<<2];
dl a[nn];
void build(ll p,ll l,ll r)
{
    if(l == r)
    {
        t[p].sum = a[l];
        t[p].v = a[l] * a[l];
        return;
    }
    build(lp,l,mid);
    build(rp,mid+1,r);
    up;
}
void down(ll p,ll l,ll r)
{
    if(!t[p].add) return;
    t[lp].add += t[p].add;
    t[rp].add += t[p].add;
    t[lp].v +=(2.0*t[lp].sum*t[p].add + t[p].add*t[p].add*(mid-l+1)*1.0);
    t[lp].sum+=(1.0*(mid-l+1)*t[p].add*1.0);
    t[rp].v +=(2.0*t[rp].sum*t[p].add + 1.0*t[p].add*t[p].add*(r-mid)*1.0);
    t[rp].sum+=(1.0*(r-mid)*t[p].add*1.0);
    t[p].add = 0;
    return;
}
void modify(ll p,ll l,ll r,ll L,ll R,dl v)
{
    if(L<=l && r<=R)
    {
        t[p].v+=(2.0*t[p].sum*v + 1.0*v*v*(r-l+1)*1.0);
        t[p].sum+=(1.0*v*(r-l+1)*1.0);
        t[p].add+=v;
        return;
    }
    down(p,l,r);
    if(L<=mid) modify(lp,l,mid,L,R,v);
    if(R>mid) modify(rp,mid+1,r,L,R,v);
    up;
    return;
}
dl query_sum(ll p,ll l,ll r,ll L,ll R)
{
    if(L<=l && r<=R) return t[p].sum;
    down(p,l,r);
    dl res = 0;
    if(L<=mid) res+=query_sum(lp,l,mid,L,R);
    if(R>mid) res+=query_sum(rp,mid+1,r,L,R);
    return res;
}
dl query_sum2(ll p,ll l,ll r,ll L,ll R)
{
    if(L<=l && r<=R) return t[p].v;
    down(p,l,r);
    dl res = 0;
    if(L<=mid) res+=query_sum(lp,l,mid,L,R);
    if(R>mid) res+=query_sum(rp,mid+1,r,L,R);
    return res;
}
ll n,m;
void solve()
{
    scanf("%lld%lld",&n,&m);
    rep(i,1,n) scanf("%Lf",&a[i]);
    build(1,1,n);
    int op,x,y;
    dl z;
    rep(i,1,m)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1)
        {
            scanf("%Lf",&z);
            modify(1,1,n,x,y,z);
        }
        else
        {
            if(op == 2)
            {
                dl res = query_sum(1,1,n,x,y);
                res = res/(1.0*(y-x+1)*1.0);
                printf("%.4Lf\n",res);
            }
            else
            {
                dl res1 = query_sum(1,1,n,x,y);
                dl res = 0;
                dl res2 = query_sum2(1,1,n,x,y);
                // res = res/((y-x+1)*1.0);
                // res2 = res2/((y-x+1)*1.0);
                res = (res2-2.0*res1/(y-x+1)*res1+1.0*res1*res1/(y-x+1)*1.0)/(1.0*(y-x+1))*1.0;
                printf("%.4Lf\n",res);
            }
        }
    }
}
int main()
{
    solve();
    return 0;
}
2023/3/21 20:20
加载中...