题解：P16799 [蓝桥杯 2026 国 B] 实验数据

· · 题解

@Daniel_100 最爱的题。

单点修改，区间查询，考虑线段树。

首先区间平均数很好求，维护区间和再除以长度就可以了。直接暴力计算方差会超时，先展开方差公式：

\begin{aligned} \mathrm{Var} &= \sum_{i=l}^r (a_i-\bar{a})^2 \\ &= \sum a_i^2 - 2\bar{a}\sum a_i + \mathit{len}\cdot \bar{a}^2 \end{aligned}

设：

代入 \bar{a} = \dfrac{S_1}{\mathit{len}}，化简得：

\mathrm{Var} = S_2 - \frac{S_1^2}{\mathit{len}}

所欲我们只用维护区间和，区间平方和就可以了。

模数 998244353 是质数，根据费马小定理：

x^{-1} \equiv x^{998244353-2} \pmod{998244353}

可用快速幂求逆元。

代码十分丑陋。

#include <iostream>

using namespace std;

#define int long long

const int mod = 998244353;
const int maxn = 3e5 + 10;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

int sum[maxn << 2], sq[maxn << 2];//分别维护区间和，区间平方和
//由于是单点修改不用懒标记
int a[maxn];

int qpow(int b, int e) {
    int res = 1;
    while (e) {
        if (e & 1) res = res * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return res;
}

void update1(int id) {
    sum[id] = (sum[id << 1] + sum[id << 1 | 1]) % mod;
}

void update2(int id) {
    sq[id] = (sq[id << 1] + sq[id << 1 | 1]) % mod;
}

void build1(int id, int left, int right) {
    if (left == right) {
        sum[id] = a[left] % mod;
        return ;
    }
    int mid = (left + right) >> 1;
    build1(id << 1, left, mid);
    build1(id << 1 | 1, mid + 1, right);
    update1(id);
}

void build2(int id, int left, int right) {
    if (left == right) {
        sq[id] = a[left] * a[left] % mod;
        return ;
    }
    int mid = (left + right) >> 1;
    build2(id << 1, left, mid);
    build2(id << 1 | 1, mid + 1, right);
    update2(id);
}

void change1(int id, int left, int right, int pos, int val) {
    if (left == right) {
        sum[id] = val % mod;
        return ;
    }
    int mid = (left + right) >> 1;
    if (pos <= mid) change1(id << 1, left, mid, pos, val);
    else change1(id << 1 | 1, mid + 1, right, pos, val);
    update1(id);
}

void change2(int id, int left, int right, int pos, int val) {
    if (left == right) {
        sq[id] = val * val % mod;
        return ;
    }
    int mid = (left + right) >> 1;
    if (pos <= mid) change2(id << 1, left, mid, pos, val);
    else change2(id << 1 | 1, mid + 1, right, pos, val);
    update2(id);
}

int query1(int id, int left, int right, int _l, int _r) {
    if (_r < left || _l > right) return 0;
    if (_l <= left && right <= _r) return sum[id];
    int mid = (left + right) >> 1;
    return (query1(id << 1, left, mid, _l, _r) + query1(id << 1 | 1, mid + 1, right, _l, _r)) % mod;
}

int query2(int id, int left, int right, int _l, int _r) {
    if (_r < left || _l > right) return 0;
    if (_l <= left && right <= _r) return sq[id];
    int mid = (left + right) >> 1;
    return (query2(id << 1, left, mid, _l, _r) + query2(id << 1 | 1, mid + 1, right, _l, _r)) % mod;
}

signed main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read() % mod;
    }
    build1(1, 1, n);
    build2(1, 1, n);
    while (m--) {
        int op = read();
        if (op == 1) {
            int l = read(), r = read();
            int len = r - l + 1;
            int s1 = query1(1, 1, n, l, r);
            int s2 = query2(1, 1, n, l, r);
            int inv = qpow(len, mod - 2);
            cout << s1 * inv % mod << ' ' << (s2 - s1 * s1 % mod * inv % mod + mod) % mod << '\n';  //这里为了防止取模后是负数
        } else {
            int pos = read(), val = read();
            change1(1, 1, n, pos, val);
            change2(1, 1, n, pos, val);
        }
    }
}