全WA求助线段树qwq
  • 板块P1471 方差
  • 楼主Kketchup
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/11/2 20:29
  • 上次更新2023/11/2 22:10:21
查看原帖
全WA求助线段树qwq
551760
Kketchup楼主2023/11/2 20:29

rt 样例过但全WA,看大家的错误都跟我不一样,求助

另附WA数据

Input:

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.7566713364794850E+0000
1 2 8  2.1308819339610636E+0000
1 1 6  1.5912831262685359E+0000
1 1 8 -2.7779214559122920E+0000
1 1 8 -6.5134523715823889E-0001
3 2 8
1 1 6 -8.5440817382186651E-0001
3 2 8
2 2 8
3 2 7
1 3 8 -1.8737916438840330E+0000
1 1 7  2.5193137815222144E+0000
1 3 8  1.2835426828823984E+0000
3 3 8

Output:

7.4145
5.2609
6.2101
1.8256
6.1810
5.8854

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int N=1e5+10;
int n,m;
double a[N];

#define ls p<<1
#define rs p<<1|1
struct tree{
    int l,r;
    double dat1,dat2,lazy;
}t[N<<2];

inline void pushup(int p){
    t[p].dat1=(t[ls].dat1+t[rs].dat1);
    t[p].dat2=(t[ls].dat2+t[rs].dat2);
}
inline void pushdown(int p){
    if(t[p].lazy){
        t[ls].dat2+=2*t[p].lazy*t[p].dat1+(t[ls].r-t[ls].l+1)*t[p].lazy*t[p].lazy;
        t[rs].dat2+=2*t[p].lazy*t[p].dat1+(t[rs].r-t[rs].l+1)*t[p].lazy*t[p].lazy;
        t[ls].dat1+=(t[ls].r-t[ls].l+1)*t[p].lazy;
        t[rs].dat1+=(t[rs].r-t[rs].l+1)*t[p].lazy;
        t[ls].lazy+=t[p].lazy;
        t[rs].lazy+=t[p].lazy;
        t[p].lazy=0;
    }
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].dat1=a[l];
        t[p].dat2=t[p].dat1*t[p].dat1;
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(p);
}
void update(int p,int l,int r,double k){
    if(l<=t[p].l&&t[p].r<=r){
        t[p].dat2+=2*k*t[p].dat1+k*k*(r-l+1);
        t[p].dat1+=(r-l+1)*k;
        t[p].lazy+=k;
        return ;
    }pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) update(ls,l,r,k);
    if(mid+1<=r) update(rs,l,r,k);
    pushup(p);
}
double query1(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].dat1;
    }pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    double ans=0;
    if(l<=mid) ans+=query1(ls,l,r);
    if(mid+1<=r) ans+=query1(rs,l,r);
    return ans;
}
double query2(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].dat2;
    }pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    double ans=0;
    if(l<=mid) ans+=query2(ls,l,r);
    if(mid+1<=r) ans+=query2(rs,l,r);
    return ans;
}
int op,x,y;
double k;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%lf",&a[i]);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            scanf("%lf",&k);
            update(1,x,y,k);
        }else if(op==2){
            double ans1=query1(1,x,y)/(y-x+1);
            printf("%.4lf\n",ans1);
        }else{
            double ans1=query2(1,x,y)/(y-x+1);
            double ans2=query1(1,x,y)/(y-x+1);
            double ans=ans1-ans2*ans2;
            printf("%.4lf\n",ans);
        }
    }
    return 0;
}

2023/11/2 20:29
加载中...