概述
题目
题目背景
出题人并没有能力写有趣的题面……
题目描述
对于一个长度为 nn 的序列 a_1,a_2,a_3cdots a_na
1
,a
2
,a
3
⋯a
n
，我们定义它的平均数 aa 为:
a=frac{1}{n}sum_{i=1}^{n}a_i
a=
n
1
i=1
∑
n
a
i
并定义它的方差 dd 为:
d=frac{1}{n}sum_{i=1}{n}(a_i-a)2
d=
n
1
i=1
∑
n
(a
i
−a)
2
现在给定一个长度为 nn 的序列 b_1,b_2cdots b_nb
1
,b
2
⋯b
n
。你需要支持两种操作。每种操作的格式为 c x y。
若 c=1c=1，为修改操作，代表将 b_xb
x
赋值为 yy。
若 c=2c=2，为查询操作，代表查询 b_xb
x
到 b_yb
y
的方差。
为了避免浮点数误差，请以分数取模形式输出结果（对 1000000007（10^9+710
9
+7）取模）。
输入格式
第一行两个整数 n,mn,m，代表序列 bb 的长度为 nn，有 mm 个操作。
第二行 nn 个整数 b_ib
i
，表示序列 bb 的初始值。
下面有 mm 行整数，每行格式为 c a b，含义如上文所示。保证所有操作合法。
输出格式
对于每个操作 2，输出一行。
输入输出样例
输入 #1复制
4 8
0 0 0 0
1 1 1
1 2 2
1 3 3
1 4 4
2 1 1
2 1 2
2 1 3
2 1 4
输出 #1复制
0
250000002
666666672
250000003
说明/提示
样例 1 解释
四次修改后，序列 bb 为：{1,2,3,4}{1,2,3,4}。
区间 [1,1][1,1] 的方差为 00。
区间 [1,2][1,2] 的方差为 frac{1}{4}
4
1
。44 的逆元为 250000002250000002。
区间 [1,3][1,3] 的方差为 frac{2}{3}
3
2
。33 的逆元为 333333336333333336，2times333333336bmod M=6666666722×333333336modM=666666672。
数据规模与约定
对于 50%50% 的数据，nleq 1000n≤1000，mleq 1000m≤1000。
对于 100%100% 的数据，1leq n,mleq 1times 10^51≤n,m≤1×10
5
，1leq b_ileq 1times 10^91≤b
i
≤1×10
9
，1leq xleq n1≤x≤n。对于操作 1，1leq yleq 1times 10^91≤y≤1×10
9
。对于操作2，xleq yleq nx≤y≤n。
思路
将方差公式化简，有
n
d
=
∑
i
=
1
n
(
b
i
−
b
‾
)
2
=
∑
i
=
1
n
(
b
i
2
−
2
b
i
b
‾
+
b
‾
2
)
=
∑
i
=
1
n
b
i
2
−
2
n
b
‾
∑
i
=
1
n
b
i
+
n
b
‾
2
nd=sum_{i=1}^n (b_i-overline{b})^2 =sum_{i=1}^n (b_i^2-2b_ioverline{b}+overline{b}^2)=sum_{i=1}^nb_i^2-2noverline{b}sum_{i=1}^nb_i+n overline{b}^2
nd=∑i=1n(bi−b)2=∑i=1n(bi2−2bib+b2)=∑i=1nbi2−2nb∑i=1nbi+nb2
由
b
‾
=
∑
i
=
1
n
b
i
n
overline{b}=frac{sum_{i=1}^n b_i}{n}
b=n∑i=1nbi
n
d
=
∑
i
=
1
n
b
i
2
−
2
(
∑
i
=
1
n
b
i
)
2
+
(
∑
i
=
1
n
b
i
)
2
n
nd=sum_{i=1}^n b_i^2-2{(sum_{i=1}^n b_i)}^2+frac{{(sum_{i=1}^n b_i)}^2}{n}
nd=∑i=1nbi2−2(∑i=1nbi)2+n(∑i=1nbi)2
所以
n
2
d
=
n
∑
i
=
1
n
b
i
2
−
2
n
(
∑
i
=
1
n
b
i
)
2
+
(
∑
i
=
1
n
b
i
)
2
n^2 d=nsum_{i=1}^n b_i^2-2n{(sum_{i=1}^n b_i)}^2+{(sum_{i=1}^n b_i)}^2
n2d=n∑i=1nbi2−2n(∑i=1nbi)2+(∑i=1nbi)2
维护区间和以及区间平方和即可
代码
#include<btis/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 1e9+7;
const ll maxn = 1e5+3;
ll a[maxn],sumv1[maxn<<4],sumv2[maxn<<4],in[maxn],n,m;
inline void pushup(ll o)
{
sumv1[o] = (sumv1[o<<1]+sumv1[o<<1|1])%p;
sumv2[o] = (sumv2[o<<1]+sumv2[o<<1|1])%p;
}
inline void build(ll o,ll l,ll r)
{
if(l==r)
{
sumv1[o] = a[l]%p;
sumv2[o] = a[l]*a[l]%p;
return ;
}
ll mid = (l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
void change(ll o,ll l, ll r,ll q,ll v)
{
if(l==r)
{
sumv1[o] = v%p;
sumv2[o] = v*v%p;
return ;
}
ll mid = (l+r)>>1;
if(q<=mid)
change(o<<1,l,mid,q,v);
else
change(o<<1|1,mid+1,r,q,v);
pushup(o);
}
ll query1(ll o,ll l,ll r,ll ql,ll qr)
{
if(ql<=l&&r<=qr)
return sumv1[o]%p;
ll ans = 0;
ll mid = (l+r)>>1;
if(ql<=mid)
ans += query1(o<<1,l,mid,ql,qr)%p;
if(qr>mid)
ans += query1(o<<1|1,mid+1,r,ql,qr)%p;
return ans%p;
}
//区间平方和
ll query2(ll o,ll l,ll r,ll ql,ll qr)
{
if(ql<=l&&r<=qr)
return sumv2[o]%p;
ll ans = 0;
ll mid = (l+r)>>1;
if(ql<=mid)
ans += query2(o<<1,l,mid,ql,qr)%p;
if(qr>mid)
ans += query2(o<<1|1,mid+1,r,ql,qr)%p;
return ans%p;
}
int main()
{
scanf("%lld%lld",&n,&m);
in[1] = 1;
for(int i = 2;i<=n;++i)
in[i] = (ll)(p-p/i)*in[p%i]%p;
for(int i = 1;i<=n;++i)
scanf("%lld",&a[i]);
build(1,1,n);
while(m--)
{
ll opt,l,r;
scanf("%lld%lld%lld",&opt,&l,&r);
if(opt == 1)
change(1,1,n,l,r%p);
else
{
ll s1 = query1(1,1,n,l,r)%p,s2 = query2(1,1,n,l,r)%p,inv = in[r-l+1],tot1 = s1*inv%p,tot2 = s2*inv%p-tot1*tot1%p;
tot2 = (tot2%p+p)%p;
printf("%lldn",tot2);
}
}
return 0;
}
最后
以上就是粗犷心锁为你收集整理的【洛谷P5142】区间方差的全部内容，希望文章能够帮你解决【洛谷P5142】区间方差所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复