RE代码求条
查看原帖
RE代码求条
1126325
Indestructible楼主2024/7/26 23:58
#include<bits/stdc++.h>
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
using namespace std;
const int maxn=100006;
int n,m;
struct SegmentTree{
	double num,numpow,tag;
}tree[maxn<<2];
double num[maxn];
void build(int pl,int pr,int p){
	if (pl==pr){
		tree[p].num=num[pl];
		tree[p].numpow=num[pl]*num[pl];
		return;
	}
	int mid=(pl+pr)>>1;
	build(pl,mid,ls(p)),build(mid+1,pr,rs(p));
	tree[p].num=tree[ls(p)].num+tree[rs(p)].num;
	tree[p].numpow=tree[ls(p)].numpow+tree[rs(p)].numpow;
}
void addtag(int pl,int pr,int p,double k){
	tree[p].numpow+=tree[p].num*2*k*(pr-pl+1)+k*k*(pr+pl-1);
	tree[p].num+=(pr-pl+1)*k,tree[p].tag+=k;
}
void pushdown(int pl,int pr,int p){
	int mid=(pl+pr)>>1;
	tree[ls(p)].numpow+=tree[ls(p)].num*2*tree[p].tag*(mid-pl+1)+
						tree[p].tag*tree[p].tag*(mid-pl+1);
	tree[rs(p)].numpow+=tree[rs(p)].num*2*tree[p].tag*(pr-mid)+
						tree[p].tag*tree[p].tag*(pr-mid);
	tree[ls(p)].num+=tree[p].tag*(mid-pl+1);
	tree[rs(p)].num+=tree[p].tag*(pr-mid);
	tree[ls(p)].tag+=tree[p].tag;
	tree[rs(p)].tag+=tree[p].tag;
	tree[p].tag=0;
}
void upd(int pl,int pr,int p,int l,int r,double k){
	if (l<=pl && pr<=r){ addtag(pl,pr,p,k); return; }
	pushdown(pl,pr,p);
	int mid=(pl+pr)>>1;
	if (pl<=mid) upd(pl,mid,ls(p),l,r,k);
	if (pr>mid) upd(mid+1,pr,rs(p),l,r,k);
	tree[p].num=tree[ls(p)].num+tree[rs(p)].num;
	tree[p].numpow=tree[ls(p)].numpow+tree[rs(p)].numpow;
}
double query_sum(int pl,int pr,int p,int l,int r){
	if (l<=pl && pr<=r) return tree[p].num;
	pushdown(pl,pr,p);
	int mid=(pl+pr)>>1;
	double s=0;
	if (pl<=mid) s+=query_sum(pl,mid,ls(p),l,r);
	if (pr>mid) s+=query_sum(mid+1,pr,rs(p),l,r);
	return s;
}
double query_powsum(int pl,int pr,int p,int l,int r){
	if (l<=pl && pr<=r) return tree[p].numpow;
	pushdown(pl,pr,p);
	int mid=(pl+pr)>>1;
	double s=0;
	if (pl<=mid) s+=query_powsum(pl,mid,ls(p),l,r);
	if (pr>mid) s+=query_powsum(mid+1,pr,rs(p),l,r);
	return s;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%lf",&num[i]);
	build(1,n,1);
	for (int i=1,op,x,y,k;i<=m;i++){
		scanf("%d%d%d",&op,&x,&y);
		if (op==1) scanf("%lf",&k),upd(1,n,1,x,y,k);
		double average=query_sum(1,n,1,x,y)/(y-x+1);
		double variance=query_powsum(1,n,1,x,y)/(y-x+1)-average*average;
		if (op==2) printf("%.4lf\n",average);
		if (op==3) printf("%.4lf\n",variance);
	}
	return 0;
}
2024/7/26 23:58
加载中...