洛谷 P1471 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-21 17:19:14

发布于：北京

4阅读

0回复

0点赞

原题链接

1 题目

板子题，只不过稍微引入了一点新的概念

2.1 方差推导

$假设现在的区间长度为n，区间a为[1,n]\\ 定义 \overline a=\frac{a_1+a_2+\cdots+a_{n-1}+a_n}{n}\\ 方差=(a_1-\overline a)^2+(a_2-\overline a)^2+\cdots+(a_{n-1}-\overline a)^2+(a_n-\overline a)^2\\ =\frac{({a_1}^2+{\overline a}^2-2a_1\overline a) + ({a_2}^2+{\overline a}^2-2a_2\overline a) + \cdots +({a_{n-1}}^2+{\overline a}^2-2a_{n-1}\overline a) + ({a_n}^2+{\overline a}^2-2a_n\overline a)}{n}\\ =\frac{{a_1}^2+{a_2}^2+\cdots+{a_{n-1}}^2+{a_n}^2+n \overline a - 2 \overline a(a_1+a_2+\cdots+a_{n-1}+a_n)}{n}\\ =\frac{{a_1}^2+{a_2}^2+\cdots+{a_{n-1}}^2+{a_n}^2}{n}+\overline a -2{\overline a}^2\\ =\frac{{a_1}^2+{a_2}^2+\cdots+{a_{n-1}}^2+{a_n}^2}{n}-{\overline a}^2$

2.2 更新推导

$当区间 [1,n] 每个数都增加了 x 时：\\ 相当于 (a_1+x)^2+(a_2+x)^2+\cdots+(a_{n-1}+x)^2+(a_n+x)^2\\ =({a_1}^2+x^2+2{a_1}x) + ({a_2}^2+x^2+2{a_2}x) +\cdots +({a_{n-1}}^2+x^2+2{a_{n-1}}x)+({a_n}^2+x^2+2{a_n}x)\\ =原有的({a_1}^2+{a_2}^2+\cdots+{a_{n-1}}^2+{a_n}^2)+nx^2+2xa_1+a_2+\cdots+a_{n-1}+a_n)$

3 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define lson (i * 2),l,mid
#define rson (i * 2 + 1),mid + 1,r
#define left (i * 2),l,r
#define right (i * 2 + 1),l,r

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}
int n, m;
const int N = 1e5 + 10;
ld a[N];
struct node{
    int l, r;
    ld lazy;
    ld sum1, sum2;// sum1区间和,sum2区间平方和
}tree[N * 4];
void update(int i){
    tree[i].sum1 = tree[i * 2].sum1 + tree[i * 2 + 1].sum1;
    tree[i].sum2 = tree[i * 2].sum2 + tree[i * 2 + 1].sum2;
}
void build(int i, int l, int r){
    tree[i].l = l, tree[i].r = r;
    tree[i].lazy = 0;
    tree[i].sum1 = tree[i].sum2 = 0;
    if (l == r){
        tree[i].sum1 = a[l];
        tree[i].sum2 = a[l] * a[l];
        return ;
    }
    int mid = (l + r) / 2;
    build(lson);
    build(rson);
    update(i);
}
void pushdown(int i){
    if (tree[i].lazy){
        tree[i * 2].sum2 += (tree[i * 2].r - tree[i * 2].l + 1) * (tree[i].lazy) * (tree[i].lazy) + 2 * (tree[i].lazy) * (tree[i * 2].sum1);
        tree[i * 2 + 1].sum2 += (tree[i * 2 + 1].r - tree[i * 2 + 1].l + 1) * (tree[i].lazy) * (tree[i].lazy) + 2 * (tree[i].lazy) * (tree[i * 2 + 1].sum1);
        tree[i * 2].sum1 += (tree[i * 2].r - tree[i * 2].l + 1) * (tree[i].lazy);
        tree[i * 2 + 1].sum1 += (tree[i * 2 + 1].r - tree[i * 2 + 1].l + 1) * (tree[i].lazy);
        tree[i * 2].lazy += tree[i].lazy;
        tree[i * 2 + 1].lazy += tree[i].lazy;
        tree[i].lazy = 0;
    }
}    
void add(int i, int l, int r, ld v){
    if (tree[i].l >= l && tree[i].r <= r){
        tree[i].sum2 += (tree[i].r - tree[i].l + 1) * v * v + 2 * v * tree[i].sum1;
        tree[i].sum1 += (tree[i].r - tree[i].l + 1) * v;
        tree[i].lazy += v;
        return ;
    }
    pushdown(i);
    int mid = (tree[i].l + tree[i].r) / 2;
    if (l <= mid){
        add(left, v);
    }
    if (r > mid){
        add(right, v);
    }
    update(i);
}
ld query_2(int i, int l, int r){
    if (tree[i].l >= l && tree[i].r <= r){
        return tree[i].sum1;
    }
    pushdown(i);
    ld temp = 0;
    int mid = (tree[i].l + tree[i].r) / 2;
    if (l <= mid){
        temp += query_2(left);
    }
    if (r > mid){
        temp += query_2(right);
    }
    return temp;
}
ld query_3(int i, int l, int r){
    if (tree[i].l >= l && tree[i].r <= r){
        return tree[i].sum2;
    }
    pushdown(i);
    ld temp = 0;
    int mid = (tree[i].l + tree[i].r) / 2;
    if (l <= mid){
        temp += query_3(left);
    }
    if (r > mid){
        temp += query_3(right);
    }
    return temp;
}

int main(){

    n = read(), m = read();
    for (int i = 1;i <= n;i++){
        scanf("%Lf", &a[i]);
    }
    build(1, 1, n);
    for (int i = 1;i <= m;i++){
        int op;
        op = read();
        if (op == 1){
            int x, y;
            ld k;
            x = read(), y = read();
            scanf("%Lf", &k);
            add(1, x, y, k);
        }
        if (op == 2){
            int x, y;
            x = read(), y = read();
            ld ans = query_2(1, x, y) / (y - x + 1);
            printf("%.4Lf\n", ans);
        }
        if (op == 3){
            int x, y;
            x = read(), y = read();
            ld qu3 = query_3(1, x, y) / (y - x + 1);
            ld qu2 = query_2(1, x, y) / (y - x + 1);
            ld ans = qu3 - qu2 * qu2;
            printf("%.4Lf\n", ans);
        }
    }
    
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

1 题目

2.1 方差推导

2.2 更新推导

3 最终代码（禁止抄袭，仅用于参考）

热门讨论