40pts求大佬帮助
  • 板块P1471 方差
  • 楼主liujinxv123
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/20 17:54
  • 上次更新2024/7/20 19:35:01
查看原帖
40pts求大佬帮助
1149762
liujinxv123楼主2024/7/20 17:54

代码40分,样例已过,预估为精度问题,求帮助。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; 
struct node{
	int l,r;
    double sum,lazy;
}t1[N << 2],t2[N << 2];
double a[N];
void build(int p,int l,int r){
	t1[p].l = l,t1[p].r = r;
	t2[p].l = l,t2[p].r = r;
    if(l == r){
        t1[p].sum = a[l];
        t2[p].sum = a[l] * a[l];
        return;	
    }
    int mid = (l + r) >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
    t1[p].sum = t1[p << 1].sum + t1[p << 1 | 1].sum;	
    t2[p].sum = t2[p << 1].sum + t2[p << 1 | 1].sum;	
}
void pushdown(int p){
    int mid = (t1[p].l + t1[p].r) >> 1;
    t1[p << 1].lazy += t1[p].lazy;
    t1[p << 1].sum += (mid - t1[p].l + 1) * t1[p].lazy;
    t1[p << 1 | 1].lazy += t1[p].lazy;
    t1[p << 1 | 1].sum += (t1[p].r - mid) * t1[p].lazy;	
    t1[p].lazy = 0; 
    t2[p << 1].lazy += t2[p].lazy;
    t2[p << 1].sum += t1[p << 1].sum * (t2[p].lazy * 2) + (mid - t1[p].l + 1) * (t2[p].lazy * t2[p].lazy);
    t2[p << 1 | 1].lazy += t2[p].lazy;
    t2[p << 1 | 1].sum += t1[p << 1 | 1].sum * (t2[p].lazy * 2) + (t1[p].r - mid) * (t2[p].lazy * t2[p].lazy);
    t2[p].lazy = 0;
}
void modify(int p,int l,int r,double c){
    if(l <= t1[p].l && t1[p].r <= r){
        t2[p].lazy += c;
        t2[p].sum += t1[p].sum * (c * 2) + (t1[p].r - t1[p].l + 1) * (c * c);
        t1[p].lazy += c;
        t1[p].sum += (t1[p].r - t1[p].l + 1) * c;
        return;
    }
    if(t1[p].lazy || t2[p].lazy) pushdown(p); 
    int mid = (t1[p].l + t1[p].r) >> 1; 
    if(l <= mid) modify(p << 1,l,r,c);
    if(r > mid) modify(p << 1 | 1,l,r,c);
    t1[p].sum = t1[p << 1].sum + t1[p << 1 | 1].sum;	
    t2[p].sum = t2[p << 1].sum + t2[p << 1 | 1].sum;	
}
double query(node tree[],int p,int l,int r){
    if(l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(tree[p].lazy) pushdown(p);
    double ans = 0;
    if(l <= mid) ans = ans + query(tree,p << 1,l,r);
    if(r > mid) ans = ans + query(tree,p << 1 | 1,l,r);	
    return ans;
}
int main(){
	int n,m;
    cin >> n >> m;
	for(int i = 1;i <= n;i ++) cin >> a[i];
    build(1,1,n);
    while(m --){
    	int op,l,r;
    	double c;
        cin >> op >> l >> r;
        int len = r - l + 1;
        if(op == 1){
            cin >> c;
            modify(1,l,r,c);
        }else if(op == 2) printf("%.4lf\n",query(t1,1,l,r) / len);
        else printf("%.4lf\n",(query(t2,1,l,r) / len * 1.0) - (query(t1,1,l,r) / len * 1.0) * (query(t1,1,l,r) / len * 1.0));
    }
}
2024/7/20 17:54
加载中...