萌新树状数组40pts,求调QAQ
  • 板块P1471 方差
  • 楼主DZDdzd
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/4 00:23
  • 上次更新2023/11/2 22:47:25
查看原帖
萌新树状数组40pts,求调QAQ
357170
DZDdzd楼主2023/9/4 00:23

方差处理和计算的部分写错了,求调悬关。

码风不喜勿喷。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define int long long

const int N = 1e5 + 5;

int n , m;
double a[N];
double tr1[N] , tr2[N] , tr3[N] , tr4[N];
//tr1 和 tr3: 维护区间和 
//tr2 和 tr4:维护区间平方和 

int lowbit(int x){
	return x & -x;
}

void add(double tr[] , int x , double c){
	for(int i = x;i <= n;i += lowbit(i)) tr[i] += c;
}

double sum(double tr[] , int x){
	double res = 0.0;
	for(int i = x;i;i -= lowbit(i)) res += tr[i];
	return res;
}

double prefix1(int x){
	return sum(tr1 , x) * (x + 1) - sum(tr3 , x);
}

double prefix2(int x){
	return sum(tr2 , x) * (x + 1) - sum(tr4 , x);
}

signed main(){
    scanf("%lld %lld" , &n , &m);
    for(int i = 1;i <= n;i ++){
    	scanf("%lf" , &a[i]);
    }
    
    //tr内 维护差分
    for(int i = 1;i <= n;i ++) add(tr1 , i , a[i] - a[i - 1]);
    for(int i = 1;i <= n;i ++) add(tr2 , i , a[i] * a[i] - a[i - 1] * a[i - 1]);
    for(int i = 1;i <= n;i ++) add(tr3 , i , (double)i * 1.0 * (a[i] - a[i - 1]));
    for(int i = 1;i <= n;i ++) add(tr4 , i , (double)i * 1.0 * (a[i] * a[i] - a[i - 1] * a[i - 1]));
    
    while(m --){
    	int opt;
    	int l , r;
    	double d;
    	
    	scanf("%lld" , &opt);
    	scanf("%lld %lld" , &l , &r);
    	if(opt == 1){
    		scanf("%lf" , &d);
    		add(tr1 , l , d) , add(tr1 , r + 1 , -d);
    		
    		add(tr3 , l , l * d) , add(tr3 , r + 1 , (r + 1) * (-d));
    		
    		add(tr2 , l , 2.0 * a[l] * d + d * d) , add(tr2 , r + 1 , -2.0 * a[r] * d - d * d);
    		
    		add(tr4 , l , l * (2.0 * a[l] * d + d * d)) , add(tr4 , r + 1 , (r + 1) * (-2.0 * a[r] * d - d * d));
		}
		else if(opt == 2){
			double tmp = prefix1(r) - prefix1(l - 1);
			double f = (double)(r - l + 1);
			printf("%.4lf\n" , tmp / f);
		}
		else{
			double f = (double)r - l + 1;
            double tmp = (prefix1(r) - prefix1(l - 1)) / f;
			double tmp1 = -2.0 * (prefix1(r) - prefix1(l - 1)) * tmp;
			double tmp2 = f * tmp * tmp;
			double tmp3 = prefix2(r) - prefix2(l - 1);
			double ans = (tmp1 + tmp2 + tmp3) / f;
			printf("%.4lf\n" , ans);
		}
	}
	
	return 0;
}
2023/9/4 00:23
加载中...