线段树样例过不了求助
  • 板块P1471 方差
  • 楼主Kniqht
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/16 19:55
  • 上次更新2023/10/27 11:24:58
查看原帖
线段树样例过不了求助
315205
Kniqht楼主2022/9/16 19:55

rt,目前是query函数的锅,但是我找不出来(其他可能也有问题,但是目前只涉及到query就出错了)

#include<bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll> 
#define fir first
#define sec second
#define db double 
using namespace std;
const int N=2e5+10;
int n,m;
struct Node{
    int l,r;
    ll add1,add2,sum,v;
}tr[N*4];
ll w[N];
void pushup(int u){
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	tr[u].v=tr[u<<1].v+tr[u<<1|1].v;
}
void pushdown(int u){
    Node &rt=tr[u],&lc=tr[u<<1],&rc=tr[u<<1|1];
    if(rt.add1){
		lc.add1+=rt.add1;rc.add1+=rt.add1;
    	lc.sum+=rt.add1*(lc.r-lc.l+1);
    	rc.sum+=rt.add1*(rc.r-rc.l+1);
    	rt.add1=0;
	}
    if(rt.add2){
    	lc.add2+=rt.add2;rc.add2+=rt.add2;
    	lc.v+=(ll)2*rt.add2*lc.sum+(lc.r-lc.l+1)*rt.add2*rt.add2;
    	rc.v+=(ll)2*rt.add2*rc.sum+(rc.r-rc.l+1)*rt.add2*rt.add2;
    	rt.add2=0;
	}
}
void build(int u,int l,int r){
    if(l==r){tr[u]={l,r,0,0,w[l],w[l]*w[l]};return;}
    tr[u]={l,r};
    int mid=l+r>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,ll c){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].add1+=c;
        tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*c;
        tr[u].add2+=c;
        tr[u].v+=(ll)2*tr[u].sum*c+(tr[u].r-tr[u].l+1)*c*c;
    }
    else{
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,c);
        if(r>mid) modify(u<<1|1,l,r,c);
        pushup(u);
    }
}
PII query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return PII{tr[u].sum,tr[u].v};
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    ll res=0,res1=0;
	PII t1=query(u<<1,l,r),t2=query(u<<1|1,l,r);
    if(l<=mid) res=t1.fir,res1=t1.sec;
    if(r>mid) res+=t2.fir,res1+=t2.sec;
    return PII{res,res1};
}
ll x,y,z;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    int op;
    build(1,1,n);
//    printf("%.4f\n",(db)query(1,1,4).fir);
    while(m--){
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            scanf("%lld",&z);
            modify(1,x,y,z);
        } 
        else if(op==2) printf("%.4f\n",(db)query(1,x,y).fir/(db)(y-x+1));
        else{
        	PII t=query(1,x,y);
        	db aver=(db)t.fir/(db)(y-x+1); 
        	db s=(db)t.sec-2.0*aver*(db)t.fir+(db)(y-x+1)*aver*aver;
        	printf("%.4f\n",s);
		}
    }
	return 0;
}

2022/9/16 19:55
加载中...