萌新线段树全wa求助
  • 板块P1471 方差
  • 楼主Miraii
  • 当前回复8
  • 已保存回复8
  • 发布时间2021/10/7 19:21
  • 上次更新2023/11/4 04:24:18
查看原帖
萌新线段树全wa求助
311942
Miraii楼主2021/10/7 19:21

样例过了

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=4e5+10;
double dat[N],squ[N];
int n,m,q;
double lazy[N],a[N];
template<typename T> inline T read(){
    T x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
void pushdown(int p,int l,int r){
    if(!lazy[p]) return;
    int mid=(l+r)>>1;
    squ[ls]+=2*lazy[p]*dat[ls]+(mid-l+1)*lazy[p]*lazy[p];
    squ[rs]+=2*lazy[p]*dat[rs]+(r-mid)*lazy[p]*lazy[p];
    dat[ls]+=lazy[p]*(r-mid);
    dat[rs]+=lazy[p]*(mid-l+1);
    lazy[p]=0;
}
void build(int p,int l,int r){
    if(l==r){
	dat[p]=a[l];//维护和
	squ[p]=a[l]*a[l];//维护平方和
	return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    dat[p]=dat[ls]+dat[rs];
    squ[p]=squ[ls]+squ[rs];
}
void upd(int p,int x,int y,int l,int r,double k){
    if(x<=l&&y>=r){
	squ[p]+=2*k*dat[p]+(r-l+1)*k*k;
	dat[p]+=k*(r-l+1);
	lazy[p]+=k;
	return;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) upd(ls,x,y,l,mid,k);
    if(y>mid) upd(rs,x,y,mid+1,r,k);
    dat[p]=dat[ls]+dat[rs];
    squ[p]=squ[ls]+squ[rs];
}
int qsum(int p,int x,int y,int l,int r){
    double res=0;
    if(x<=l&&y>=r) return dat[p];
    int mid=(l+r)>>1;
    pushdown(p,l,r);
    if(x<=mid) res+=qsum(ls,x,y,l,mid);
    if(y>mid) res+=qsum(rs,x,y,mid+1,r);
    return res;
}
int qsqu(int p,int x,int y,int l,int r){
    double res=0;
    if(x<=l&&y>=r) return squ[p];
    int mid=(l+r)>>1;
    pushdown(p,l,r);
    if(x<=mid) res+=qsqu(ls,x,y,l,mid);
    if(y>mid) res+=qsqu(rs,x,y,mid+1,r);
    return res;
}
signed main(){
    n=read<int>();m=read<int>();
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
	int c=read<int>(),x=read<int>(),y=read<int>();
	if(c==1){
	    double k;
	    scanf("%lf",&k);
	    upd(1,x,y,1,n,k);
	}
	else if(c==2){
	    printf("%0.4lf\n",qsum(1,x,y,1,n)/((y-x+1)*1.0));
	}
	else{
	    printf("%0.4lf\n",qsqu(1,x,y,1,n)/((y-x+1)*1.0)-(qsum(1,x,y,1,n)/((y-x+1)*1.0))*(qsum(1,x,y,1,n)/((y-x+1)*1.0)));
	}
    }
    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.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

输出

8.7344
4.1020
7.4286
5.0000
7.8889
11.3889

应该输出

7.4145
5.2609
6.2101
1.8256
6.1810
5.8854
2021/10/7 19:21
加载中...