求助线段树过不了
  • 板块P1471 方差
  • 楼主phigy
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/12/18 23:45
  • 上次更新2023/11/5 05:58:14
查看原帖
求助线段树过不了
115359
phigy楼主2020/12/18 23:45

样例第三问输出1.6应输出0.8

#include <iostream>
#include <cstdio>

#define int long long

using namespace std;

int n,m,p;
double a[1000000];
struct tree
{
    double s,p,lazy;
}t[2000000];

int up(int o)
{
    t[o].s=t[o*2].s+t[o*2+1].s;
    t[o].p=t[o*2].p+t[o*2+1].p;
}

int down(int o,int l,int r)
{
    if(!t[o].lazy)return 0;
    int mid=(l+r)/2;
    t[o*2].s+=t[o*2].s+(mid-l+1)*t[o].lazy;
    t[o*2+1].s+=t[o*2+1].s+(r-mid)*t[o].lazy;

    t[o*2].p+=t[o*2].p+2*t[o].lazy*t[o*2].s+(mid-l+1)*t[o].lazy*t[o].lazy;
    t[o*2+1].p+=t[o*2+1].p+2*t[o].lazy*t[o*2+1].s+(r-mid)*t[o].lazy*t[o].lazy;

    t[o*2].lazy+=t[o].lazy;
    t[o*2+1].lazy+=t[o].lazy;

    t[o].lazy=0;
}

int build(int o,int l,int r)///建树
{
    if(l==r)
    {
        t[o].s=a[l];
        t[o].p=a[l]*a[l];
    }
    else
    {
        int mid=(l+r)/2;
        build(o*2,l,mid);
        build(o*2+1,mid+1,r);
        up(o);
    }
    return 0;
}


int add(int o,int l,int r,int x,int y,double z)
{

    if(x<=l&&r<=y)
    {
        t[o].lazy+=z;
        t[o].s=t[o].s+(r-l+1)*z;
        t[o].p=t[o].p+2*z*t[o].s+(r-l+1)*z*z;
        return 0;
    }
    int mid=(l+r)/2;
    down(o,l,r);
    if(x<=mid)add(o*2,l,mid,x,y,z);
    if(y>mid)add(o*2+1,mid+1,r,x,y,z);
    up(o);
    return 0;
}

double query_num(int o,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return t[o].s;
    down(o,l,r);
    double ans=0;
    int mid=(l+r)/2;
    if(x<=mid)ans+=query_num(o*2,l,mid,x,y);
    if(y>mid)ans+=query_num(o*2+1,mid+1,r,x,y);
    return ans;
}

double query_pow(int o,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return t[o].p;
    down(o,l,r);
    double ans=0;
    int mid=(l+r)/2;
    if(x<=mid)ans+=query_pow(o*2,l,mid,x,y);
    if(y>mid)ans+=query_pow(o*2+1,mid+1,r,x,y);
    return ans;
}
signed main()
{
    int i,j,k;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        int od,x,y;
        double z;
        cin>>od;
        if(od==1)
        {
            cin>>x>>y>>z;
            add(1,1,n,x,y,z);
        }
        if(od==2)
        {
            cin>>x>>y;
            double ans1=query_num(1,1,n,x,y)/(y-x+1);
            printf("%.4lf\n",ans1);
        }
        if(od==3)
        {
            cin>>x>>y;
            double ans1=(query_pow(1,1,n,x,y)*1.0)/((y-x+1)*1.0),ans2=(query_num(1,1,n,x,y)*1.0)/((y-x+1)*1.0);
            double ans=ans1-ans2*ans2;
            printf("%.4lf\n",ans);
        }
    }
    return 0;
}
/*
8 15
8.46 6.03 3.73 0.32 7.43 3.71 8.04 8.22
3 1 8
1 2 8 -2.7566713364794850
1 2 8  2.1308819339610636
1 1 6  1.5912831262685359
1 1 8 -2.7779214559122920
1 1 8 -6.5134523715823889
3 2 8
1 1 6 -8.5440817382186651
3 2 8
2 2 8
3 2 7
1 3 8 -1.8737916438840330
1 1 7  2.5193137815222144
1 3 8  1.2835426828823984
3 3 8

*/

2020/12/18 23:45
加载中...