分块0分求助P1471
  • 板块灌水区
  • 楼主ko_no_lzx_da
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/2/22 14:44
  • 上次更新2023/10/28 07:57:38
查看原帖
分块0分求助P1471
418419
ko_no_lzx_da楼主2022/2/22 14:44
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<cmath>
#include<iomanip> 
#include<algorithm>
using namespace std;
int n,m,ks; 
int L[10000],R[10000];
double a[100000],lan[10000];
double sum[10000];
int aa[10000];
void add(int x,int y,double k){
	int xk=aa[x],yk=aa[y];
	if(xk==yk){
		for(int i=x;i<=y;i++){
			a[i]+=k;
			sum[xk]+=k;
		}
	}else if(x==L[aa[x]]&&y==R[aa[y]]){
		for(int i=aa[x];i<=aa[y];i++){
			lan[i]+=k;
			sum[i]+=(R[i]-L[i]+1)*k;
		}
	}else if(x>L[aa[x]]&&y==R[aa[y]]){
		for(int i=x;i<=R[aa[x]];i++){
			a[i]+=k;
			sum[xk]+=k;
		}
		for(int i=yk;i>xk;i--){
			lan[i]+=k;
			sum[i]+=(R[i]-L[i]+1)*k;
		}
	}else if(x==L[x]&&y<R[y]){
		for(int i=L[y];i<=y;i++){
			a[i]+=k;
			sum[yk]+=k;
		}
		for(int i=xk;i<yk;i++){
			lan[i]+=k;
			sum[i]+=(R[i]-L[i]+1)*k;
		}
	}else{
		for(int i=x;i<=R[aa[x]];i++){
			a[i]+=k;
			sum[xk]+=k;
		}
		for(int i=L[aa[y]];i<=y;i++){
			a[i]+=k;
			sum[yk]+=k;
		} 
		for(int i=xk+1;i<yk;i++){
			lan[i]+=k;
			sum[i]+=(R[i]-L[i]+1)*k;
		}
	}
}
double find(int x,int y){
	int xk=aa[x],yk=aa[y];
	double re=0;
	if(xk==yk){
		for(int i=x;i<=y;i++){
			re+=a[i]+lan[aa[i]];
		}
		return re;
	}else if(x==L[aa[x]]&&y==R[aa[y]]){
		for(int i=aa[x];i<=aa[y];i++){
			re+=lan[i]*(R[i]-L[i]+1)+sum[i];
		}
		return re;
	}else if(x>L[aa[x]]&&y==R[aa[y]]){
		for(int i=x;i<=R[aa[x]];i++){
			re+=a[i]+lan[aa[i]];
		}
		for(int i=yk;i>xk;i--){
			re+=lan[i]*(R[i]-L[i]+1)+sum[i];
		}
		return re;
	}else if(x==L[x]&&y<R[y]){
		for(int i=L[y];i<=y;i++){
			re+=a[i]+lan[aa[i]];
		}
		for(int i=xk;i<yk;i++){
			re+=lan[i]*(R[i]-L[i]+1)+sum[i];
		}
		return re;
	}else{
		for(int i=x;i<=R[aa[x]];i++){
			re+=a[i]+lan[aa[i]];
		}
		for(int i=L[aa[y]];i<=y;i++){
			re+=a[i]+lan[aa[i]];
		} 
		for(int i=xk+1;i<yk;i++){
			re+=lan[i]*(R[i]-L[i]+1)+sum[i];
		}
		return re;
	}
}
int main(){
	cin >>n>>m;
	ks=sqrt(n);
	for(int i=1;i<=ks;i++){
		L[i]=(i-1)*ks+1;
		R[i]=i*ks;
	}
	if(R[ks]<n){
		ks++;
		L[ks]=R[ks-1]+1;
		R[ks]=n;
	}
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	for(int i=1;i<=ks;i++){
		for(int j=L[i];j<=R[i];j++){
        	aa[j]=i;
        	sum[i]+=a[j];
		}
	}
	for(int i=1;i<=m;i++){
		int t,xx,yy;
		double kk;
		cin >>t;
		if(t==1){
			cin >>xx>>yy>>kk;
			add(xx,yy,kk);
//			for(int i=1;i<=n;i++){
//				cout <<a[i]+lan[aa[i]]<<" ";
//			}
//			cout <<endl; 
		}
		if(t==2){
			cin >>xx>>yy;
			cout <<fixed<<setprecision(4)<<find(xx,yy)/(yy-xx+1)<<endl;
		}
		if(t==3){
			cin >>xx>>yy;
			double qwq=find(xx,yy)/(yy-xx+1),he=0;
			for(int i=xx;i<=yy;i++){
				he+=(a[i]-qwq)*(a[i]-qwq);
			}
			cout <<fixed<<setprecision(4)<<he/(yy-xx+1)<<endl;
		}
	}
	return 0;
}
//0 1 2 3 4



2022/2/22 14:44
加载中...