[luogu5142]区间方差

前言

略

题目相关

链接

题目大意

单点修改，区间方差

数据范围

$n,q\le 100000$

题解

区间方差的定义
$$\frac{1}{r-l+1}\sum _{i=l}^r(a_i-a{)}^2$$
其中$$a=\frac{1}{r-l+1}\sum _{i=l}^r{a}_i$$
直接展开1式
$$\begin{array}{rl}Ans& =\frac{1}{r-l+1}\sum _{i=l}^r(a_i-a{)}^2\\ & =\frac{1}{r-l+1}\sum _{i=l}^r(a_i^2-2a_{i}a+a^2)\end{array}$$
第三项求$a$很方便，区间求和即可
我们发现，第二项可以直接套用区间求和的结果，乘起来即可
第一项是区间平方和，直接维护
两个BIT维护区间和和平方和即可

代码

#include<bits/stdc++.h> typedef long long ll; #define rg register template <typename T> inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;} template <typename T> inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');} template <typename T> inline void print(const T x){if(x<0)putchar('-'),printe(-x);else printe(x);} inline int lowbit(const int x){return x&(-x);} const int mod=1000000007; void md(int &x){if(x>=mod)x-=mod;} int Md(const int x){return x>=mod?x-mod:x;} inline ll pow(ll x,ll y) {ll res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res; } int n,m,v[100001]; struct BIT {int a[100001];inline void add(int u,const int v){while(u<=n)md(a[u]+=v),u+=lowbit(u);}inline int query(int u){ll res=0;while(u)res+=a[u],u-=lowbit(u);return res%mod;} }A,B; int main() {read(n),read(m);for(rg int i=1;i<=n;i++)read(v[i]),A.add(i,v[i]),B.add(i,(ll)v[i]*v[i]%mod);for(rg int i=1;i<=m;i++){int opt,a,b;read(opt),read(a),read(b);if(opt==1)A.add(a,mod-v[a]),B.add(a,mod-(ll)v[a]*v[a]%mod),v[a]=b,A.add(a,v[a]),B.add(a,(ll)v[a]*v[a]%mod);else{a--;const int lenth=b-a,inv=pow((ll)lenth,mod-2);const int q=Md(mod+A.query(b)-A.query(a)),p=(ll)q*inv%mod;print((ll)(mod+mod+(ll)p*p%mod*lenth%mod-(ll)q*p%mod*2%mod+B.query(b)-B.query(a))%mod*inv%mod),putchar('\n');}}return 0; }

总结

模板题，增强信心（大雾）

总结

以上是生活随笔为你收集整理的[luogu5142]区间方差的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。