luoguP1471 方差

这道题一眼线段树
然而并不太好想怎么维护😭
图片引用自luogu@远航之曲

总体思路就是记录区间和，还有区间的平方和，通过图2来进行平方和的标记下传，用图一的式子来算出方差

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<stack>
#include<set>
using namespace std;
inline int read(){
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9'){
		if(c=='-')
			flag=1;
		c=getchar();
	}
    while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
    return flag?-x:x;
}
double tree1[500100];
double tree2[500100];
double lazy[500100],a[500010];
void build(int l,int r,int t){
	if(l==r){
		tree1[t]=a[l];
		tree2[t]=a[l]*a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,t*2);
	build(mid+1,r,t*2+1);
	tree1[t]=tree1[t*2]+tree1[t*2+1];
	tree2[t]=tree2[t*2]+tree2[t*2+1];
}
void push(int t,int len){
	if(lazy[t]==0)return;
	tree2[t*2]+=(len-len/2)*lazy[t]*lazy[t]+2*tree1[t*2]*lazy[t];
	tree2[t*2+1]+=(len/2)*lazy[t]*lazy[t]+2*tree1[t*2+1]*lazy[t];
	tree1[t*2]+=(len-len/2)*lazy[t];
	tree1[t*2+1]+=(len/2)*lazy[t];
	lazy[t*2]+=lazy[t];
	lazy[t*2+1]+=lazy[t];
	lazy[t]=0;
	return;
}
double ans;
void query(int ll,int rr,int l,int r,int t,int flag){
	if(ll<=l&&r<=rr){
		if(flag==1)ans+=tree1[t];
		else ans+=tree2[t]; 
		return;
	}
	push(t,r-l+1);
	int mid=(l+r)/2;
	if(ll<=mid)query(ll,rr,l,mid,t*2,flag);
	if(rr>mid)query(ll,rr,mid+1,r,t*2+1,flag);
	tree1[t]=tree1[t*2]+tree1[t*2+1];
	tree2[t]=tree2[t*2]+tree2[t*2+1];
}
void modify(int ll,int rr,int l,int r,double c,int t){
	if(ll<=l&&r<=rr){
		lazy[t]+=c;
		tree2[t]+=2*c*tree1[t]+c*c*(r-l+1);
		tree1[t]+=(r-l+1)*c;
		return;
	}
	push(t,r-l+1);
	int mid=(l+r)/2;
	if(ll<=mid)modify(ll,rr,l,mid,c,t*2);
	if(rr>mid)modify(ll,rr,mid+1,r,c,t*2+1);
	tree1[t]=tree1[t*2]+tree1[t*2+1];
	tree2[t]=tree2[t*2]+tree2[t*2+1];
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	while(m--){
		int opt;
		cin>>opt;
		if(opt==1){
			int a,b;
			double c;
			cin>>a>>b>>c;
			modify(a,b,1,n,c,1);
		}else if(opt==2){
			int a,b;
			cin>>a>>b;
			ans=0;
			query(a,b,1,n,1,1);
			double avg=ans;
			avg=avg/(b-a+1);
			printf("%.4lf\n",avg);
		}else if(opt==3){
			int a,b;
			cin>>a>>b;
			ans=0;
			query(a,b,1,n,1,1);
			double avg=ans;
			avg=avg/(b-a+1);
			ans=0;
			query(a,b,1,n,1,2);
			double sum=ans;
			sum=sum/(b-a+1);
			double ANS=sum-avg*avg;
			printf("%.4lf\n",ANS); 
		}
	}
	return 0;
}