30pts求助
  • 板块P1471 方差
  • 楼主stueam
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/8/4 15:59
  • 上次更新2023/10/27 17:03:05
查看原帖
30pts求助
250640
stueam楼主2022/8/4 15:59
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct seg
{
    double add,sum,two;
}tr[N * 4];
int n,m;
double a[N];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].two = tr[u << 1].two + tr[u << 1 | 1].two;
}
void build(int u,int l,int r)
{
    if(l == r) 
    {
        tr[u].sum = a[l];
        tr[u].two = a[l] * a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
    pushup(u);
}
void pushdown(int u,int len)
{
    seg &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
    if(root.add)
    {
        double &x = root.add;
        right.add += x;
        left.add += x;
        right.two += 2 * right.sum * x + (len - len / 2) * x * x;
        left.two += 2 * left.sum * x + len / 2 * x * x;
        right.sum += (len - len / 2) * x;
        left.sum += len / 2 * x;
        root.add = 0;
    }
}
void modify(int u,int l,int r,double x,int L,int R)
{
    if(L >= l && R <= r)
    {
        tr[u].add += x;
        tr[u].two += 2 * tr[u].sum * x + (R - L + 1) * x * x;
        tr[u].sum += x * (R- L + 1);
    }
    else
    {
        pushdown(u,R - L + 1);
        int mid = L + R >> 1;
        if(l <= mid)    modify(u << 1,l,r,x,L,mid);    
        if(r > mid)     modify(u << 1 | 1,l,r,x,mid + 1,R);
        pushup(u);
    }
}
double query1(int u,int l,int r,int L,int R)//求和
{
    if(L >= l && R <= r)    return tr[u].sum;
    pushdown(u,R - L + 1);
    int mid = L + R >> 1;
    double v = 0;
    if(l <= mid)    v = query1(u << 1,l,r,L,mid);
    if(r > mid)     v += query1(u << 1 | 1,l,r,mid + 1,R);
    
    return v;
}
double query2(int u,int l,int r,int L,int R)
{
    if(L >= l && R <= r)    return tr[u].two;
    pushdown(u,R - L + 1);
    int mid = L + R >> 1;
    double v = 0;
    if(l <= mid)    v = query2(u << 1,l,r,L,mid);
    if(r > mid)     v += query2(u << 1 | 1,l,r,mid + 1,R);
    
    return v;
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)   cin >> a[i];
    build(1,1,n);
    
    while(m--)
    {
        int opt,x,y;
        double k;
        cin >> opt >> x >> y;
        if(opt == 1)
        {
            cin >> k;
            modify(1,x,y,k,1,n);
        }
        else
        {
        	if(opt == 2)
            	printf("%.4lf\n",query1(1,x,y,1,n) / double(y - x + 1)); 
            if(opt == 3){
            	double sum1 = query2(1,x,y,1,n) / double(y - x + 1),sum2 = query1(1,x,y,1,n) / double(y - x + 1);
            	
            	printf("%.4lf\n",sum1 - sum2 * sum2);
			}
            
            
            
        }
    }
    
    return 0;
}
2022/8/4 15:59
加载中...