求助(玄关)
查看原帖
求助(玄关)
717476
Gaochenxi103_QWQ楼主2024/4/20 22:30

主要问题大概是平方和的维护错误

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node{
	int l,r;
	double sum,qsum,lazy,qlazy;
}tree[4*N];
int n,m;
double a[N];
void Lazy(int root,double k)
{
	tree[root].lazy+=k;
	tree[root].sum+=(tree[root].r-tree[root].l+1)*k;
}

void qLazy(int root,double k)
{
    int l=tree[root].l,r=tree[root].r;
	tree[root].qlazy+=k*k;
	tree[root].qsum+=2*k*tree[root].sum+(r-l+1)*k*k;//求助 
}
void pushdown(int root,int l,int r)
{
	if(tree[root].lazy!=0)
	{
		Lazy(root*2,tree[root].lazy);
		Lazy(root*2+1,tree[root].lazy);
		tree[root].lazy=0;
	}
	if(tree[root].qlazy!=0)
	{
		qLazy(root*2,tree[root].qlazy);
		qLazy(root*2+1,tree[root].qlazy);
		tree[root].qlazy=0;
	}
		
} 
void build_lintree(int root,int l,int r)
{
	tree[root].l=l,tree[root].r=r;
	if(l==r)
	{
		tree[root].sum=a[l];
		tree[root].qsum=(a[l]*a[l]);
		return ;
	}
	int mid=(l+r)/2;
	build_lintree(root*2,l,mid);
	build_lintree(root*2+1,mid+1,r);
	tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
	tree[root].qsum=tree[root*2].qsum+tree[root*2+1].qsum;
	
}
void updata(int root,int l,int r,double k)
{
	if(tree[root].l>=l && tree[root].r<=r)
	{
		Lazy(root,k);
		qLazy(root,k);
		return ;
	}
	pushdown(root,l,r);
	int mid=(tree[root].l+tree[root].r)/2;
	if(l<=mid)
	{
		updata(root*2,l,r,k);
	}
	if(r>mid)
	{
		updata(root*2+1,mid+1,r,k);
	}
	tree[root].sum=tree[root*2].sum+tree[root*2+1].sum;
	tree[root].qsum=tree[root*2].qsum+tree[root*2+1].qsum;

}
double query_sum(int root,int l,int r)
{
	if(tree[root].l>=l && tree[root].r<=r)
	{
		pushdown(root,l,r);
		return tree[root].sum;
	}
	int mid=(tree[root].l+tree[root].r)/2;
	double cnt=0;
	if(l<=mid)
	{
		cnt+=query_sum(root*2,l,r);
	}
	if(r>mid)
	{
		cnt+=query_sum(root*2+1,l,r);
	}
	return cnt;
}
double query_qsum(int root,int l,int r)
{
	if(tree[root].l>=l && tree[root].r<=r)
	{
		pushdown(root,l,r);
		return tree[root].qsum;
	}
	int mid=(tree[root].l+tree[root].r)/2;
	double cnt=0;
	if(l<=mid)
	{
		cnt+=query_qsum(root*2,l,r);
	}
	if(r>mid)
	{
		cnt+=query_qsum(root*2+1,l,r);
	}
	return cnt;
}
void dfs(int root)
{
	if(tree[root].l==tree[root].r)
	{
		cout<<tree[root].sum<<" ";
		return ;
	}
	int mid=(tree[root].l+tree[root].r)/2;
	dfs(root*2);
	dfs(root*2+1);
}
double f(int x,int y)
{
	dfs(1);
    cout<<"\n";
    cout<<"qsum:"<<query_qsum(1,x,y)<<"\n";
    cout<<"len:"<<(abs(y-x)+1)<<"\n";
    cout<<"pa:"<<(query_sum(1,x,y)/(abs(y-x)+1))<<"\n";
	return query_qsum(1,x,y)/(abs(y-x)+1)-(query_sum(1,x,y)/(abs(y-x)+1))*(query_sum(1,x,y)/(abs(y-x)+1));
}
signed main() {
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build_lintree(1,1,n);
	while(m--)
	{
		int q,x,y;
        double k;
		cin>>q;
		if(q==1)
		{
			cin>>x>>y>>k;
			updata(1,x,y,k);
		} 
		else if(q==2)
		{
			cin>>x>>y;
			printf("%.4lf\n",query_sum(1,x,y)/(abs(y-x)+1));
		}
		else
		{
			cin>>x>>y;
			printf("%.4lf\n",f(x,y));
		}
	}
	return 0;
}


2024/4/20 22:30
加载中...