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

· · 题解

题目很清晰，就是说让你求出区间方差。

考虑将方差公式展开来。过程如下：

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

其中

\bar{a} = \frac{\sum_{i=l}^r a_i}{r-l+1}

注意到本题为单点修改区间查询，使用树状数组即可完成此题。设置两个树状数组，一个记录区间和一个记录区间平方和。

对于中间的除法运算（如求平均数），需将除法转换为逆元。

::::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define mod 998244353
#define int long long
#define pii pair<int, int>
#define endl "\n"
#define max(x, y) (x>y?x:y)
#define min(x, y) (x<y?x:y)
int n, m, a[N];
class GreenMelon{
private:
    int s[N];
    inline int lowbit(int x){ return x&(-x); }
public:
    inline void add(int k, int x){
        x%=mod;
        for(int i=k;i<=n;i+=lowbit(i)){
            s[i] = (s[i]+x)%mod;
        }
    }
    inline int query(int k){
        int ans=0;
        for(int i=k;i;i-=lowbit(i)){
            ans = (ans+s[i])%mod;
        }
        return ans;
    }
} sum, powsum;
inline int poww(int a, int b, int p){
    int ans=1;
    while(b){
        if(b&1){
            ans=ans*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
main(){
#ifdef Greenmelon
    freopen("", "r", stdin);
    freopen("", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum.add(i, a[i]);
        powsum.add(i, a[i]*a[i]%mod);
    }
    for(int i=1;i<=m;i++){
        int op, x, y;
        cin>>op>>x>>y;
        if(op==1){
            int s=(sum.query(y)-sum.query(x-1)+mod)%mod;
            int pows=(powsum.query(y)-powsum.query(x-1)+mod)%mod;
            int len=y-x+1;
            int bar=s*poww(len, mod-2, mod)%mod;
            int var=(pows-2*bar%mod*s%mod+mod)%mod;
            var=(var+bar*bar%mod*len%mod)%mod;
            cout<<bar%mod<<" "<<var%mod<<endl;
        }
        else{
            y%=mod;
            sum.add(x, (y-a[x]+mod)%mod);
            powsum.add(x, (y*y%mod-a[x]*a[x]%mod+mod)%mod);
            a[x]=y;
        }
    }
}

::::