蒟蒻求助:样例过了然而全WA
  • 板块P1471 方差
  • 楼主youdu666
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/7 15:53
  • 上次更新2023/10/27 21:36:11
查看原帖
蒟蒻求助:样例过了然而全WA
329698
youdu666楼主2022/7/7 15:53
#include<cstdio>
#include<iostream>
using namespace std;
const int N=100005;
struct kof{
    double sum,tag;
};
kof tree[N<<2],sfang[N<<2];
int n,m;
double a[N];
void build(int k,int l,int r)
{
    if(l==r)
    {
        tree[k].sum+=a[l];
        sfang[k].sum+=a[l]*a[l];
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
    sfang[k].sum=sfang[k<<1].sum+sfang[k<<1|1].sum;
    return;
}
inline void pushdown(int k,int l,int r)
{
    int mid=l+r>>1;
    if(sfang[k].tag)
    {
        sfang[k<<1].tag+=sfang[k].tag;
        sfang[k<<1|1].tag+=sfang[k].tag;
        sfang[k<<1].sum+=tree[k<<1].sum*2*sfang[k<<1].tag+(mid-l+1)*sfang[k<<1].tag*sfang[k<<1].tag;
        sfang[k<<1|1].sum+=tree[k<<1|1].sum*2*sfang[k<<1|1].tag+(r-mid)*sfang[k<<1|1].tag*sfang[k<<1|1].tag;
    }
    if(tree[k].tag)
    {
        tree[k<<1].tag=tree[k].tag;
        tree[k<<1|1].tag=tree[k].tag;
        tree[k<<1].sum+=tree[k].tag*(mid-l+1);
        tree[k<<1|1].sum+=tree[k].tag*(r-mid);
    }
    sfang[k].tag=tree[k].tag=0;
    return;
}
void update(int k,int l,int r,int x,int y,double v)
{
    if(l>y||r<x) return;
    if(l>=x&&r<=y)
    {
        sfang[k].tag+=v;
        tree[k].tag+=v;
        sfang[k].sum+=tree[k].sum*2*v+(r-l+1)*v*v;
        tree[k].sum+=v*(r-l+1);
        
        return;
    }
    pushdown(k,l,r);
    int mid=l+r>>1;
    if(x<=mid)
        update(k<<1,l,mid,x,y,v);
    if(y>mid)
        update(k<<1|1,mid+1,r,x,y,v);
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
    sfang[k].sum=sfang[k<<1].sum+sfang[k<<1|1].sum;
    return;
}
double queryba(int k,int l,int r,int x,int y)
{
    double ans=0;
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y)
        return tree[k].sum;
    pushdown(k,l,r);
    int mid=l+r>>1;
    if(x<=mid)
        ans+=queryba(k<<1,l,mid,x,y);
    if(y>mid)
        ans+=queryba(k<<1|1,mid+1,r,x,y);
    return ans;
}
double queryfc(int k,int l,int r,int x,int y)
{
    double ans=0;
    if(l>y||r<x) return 0;
    if(l>=x&&r<=y)
        return sfang[k].sum;
    pushdown(k,l,r);
    int mid=l+r>>1;
    if(x<=mid)
        ans+=queryfc(k<<1,l,mid,x,y);
    if(y>mid)
        ans+=queryfc(k<<1|1,mid+1,r,x,y);
    return ans;
}
int main()
{
    int x,y,q;
    double z;
    double ans,p;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    //printf("BUILDtest:%d\n",tree[1].sum);
    for(int i=1;i<=m;i++)
    {
        cin>>q;
        if(q==1)
        {
            cin>>x>>y>>z;
            update(1,1,n,x,y,z);
        }
        if(q==2)
        {
            cin>>x>>y;
            ans=queryba(1,1,n,x,y);
            //printf("Q2.test:%.4lf\n",ans);
            ans/=(y-x+1);
            printf("%.4lf\n",ans);
        }
        if(q==3)
        {
            cin>>x>>y;
            ans=queryfc(1,1,n,x,y);
            //printf("Q3.test:%.4lf\n",ans);
            ans/=(y-x+1);
            p=queryba(1,1,n,x,y);
            p/=(y-x+1);
            ans-=p*p;
            printf("%.4lf\n",ans);
        }
    }
}
2022/7/7 15:53
加载中...