题解 P1471 【方差】

浮尘 · 2020-03-01 09:15:49 · 题解

我发现好像没有人特别清晰地描述打懒标记这个过程, 所以特意打出了这个过程，看注释吧~~~

#include<iostream>
#include<iomanip>
using namespace std;
const int N = 100005, INF = 0x7fffffff;
double a[N], sum[4*N], sum2[4*N]; 
double tag[4*N];

void pushup(int k)
{
    sum[k] = sum[k * 2] + sum[k * 2 + 1]; //区间和
    sum2[k] = sum2[k * 2] + sum2[k * 2 + 1]; //区间平方和
    return ; 
} 

void build(int k, int lt, int rt) //第k个结点， lt rt为要询问的区间范围 
{
    if(lt == rt)
    {
        sum[k] = a[lt]; //a为原始数组，sum[k]为第k个结点的区间和 
        sum2[k] = a[lt] * a[lt]; //平方 
        return ;
    }
    int mid = lt + (rt - lt) / 2; // mid = (lt + rt) >> 1
    build(k * 2, lt, mid);
    build(k * 2 + 1, mid + 1, rt);
    pushup(k);
    return ;
}

void Add(int k, int lt, int rt, double val) //打懒标记 
{
    tag[k] += val; //标记K结点对应的区间要加的值
    sum2[k] += 2 * val * sum[k] + val * val * (rt - lt + 1); //因为平方和要用到 区间和， 所以要先更新！ 
    sum[k] += (rt - lt + 1) * val; 
    return ; 
}

void pushdown(int k, int lt, int rt)
{
    if(tag[k] == 0)
        return ;
    int mid = lt + (rt - lt) / 2;
    Add(k*2, lt, mid, tag[k]);
    Add(k*2+1, mid+1, rt, tag[k]);
    tag[k] = 0; //将标记传给子节点后，父节点的标记要清零，否则会加重复
    return ; 
}

//在qx, qy区间每个数加上val 
void modify(int k, int lt, int rt, int qx, int qy, double val)
{
    if(lt > qy || rt < qx)
        return ;
    else if(lt >= qx && rt <= qy)
    {
        Add(k, lt, rt, val);
        return ;
    }
    int mid = lt + (rt - lt) / 2;
    pushdown(k, lt, rt); 
    modify(k * 2, lt, mid, qx, qy, val);
    modify(k * 2 + 1 , mid + 1, rt, qx, qy, val);
    pushup(k);
    return ; 
}

double query(int k, int lt, int rt, int qx, int qy)
{
    if(lt > qy || rt < qx)
        return 0;
    else if(lt >= qx && rt <= qy)
        return sum[k];
    int mid = lt + (rt - lt) / 2;
    pushdown(k, lt, rt); //询问时才下传标记，因为需要知道子区间要加的值 
    return query(k * 2, lt, mid, qx, qy) + query(k * 2 + 1, mid + 1, rt, qx, qy);
}

double query2(int k, int lt, int rt, int qx, int qy)
{
    if(lt > qy || rt < qx)
        return 0;
    else if(lt >= qx && rt <= qy)
        return sum2[k];
    int mid = lt + (rt - lt) / 2;
    pushdown(k, lt, rt); //询问时才下传标记，因为需要知道子区间要加的值 
    return query2(k * 2, lt, mid, qx, qy) + query2(k * 2 + 1, mid + 1, rt, qx, qy);
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    } 
    build(1, 1, n); //建树 
    for(int i = 1; i <= m; i++)
    {
        int option, x, y;
        double v;
        cin >> option;
        if(option == 1)
        {
            cin >> x >> y >> v;
            modify(1, 1, n, x, y, v);
        }
        else if(option == 2)
        {
            cin >> x >> y;
            cout << fixed << setprecision(4) << query(1, 1, n, x, y) / (y-x+1) << "\n";
        }
        else
        {
            cin >> x >> y;
            double avg = query(1, 1, n, x, y) / (y-x+1);
            cout << fixed << setprecision(4) << -avg * avg + query2(1, 1, n, x, y) / (y-x+1) << "\n";
        }
    }
    return 0;
}