这熟悉的题面与输入
三种操作：1个修改2种查询。
足以想到我们的经典数据结构——线段树。
没有完全掌握或者不会线段树的同学可以康康我的[链接登录后可见]然后A了模板再来看这题哦
这是一道基本可以说是模板形式的线段树题目，但是难度却不低。
无非是给定序列，让你维护区间平均值与方差。
但是这道题目离谱之处在于：
不过如果了解了思路与做法后也就是多对通分约分操作进行了要求。
这是我们机房模拟赛的题目。我就顺便说说我的思路历程吧。
其实最开始我的想法是线段树，但是我想得就是直接维护方差平均值(指线段树内就存方差和平均值，我是个狼灭）。
我是怎么想的呢，我建了应该子结构体，存储分数的分子分母。顺便写了分数加分数乘以及简化分数的函数。
我仔细分析复杂度与实现难度，炸了。
然后我脑中就开始思考方差和平均值的共性，拿出草稿纸计算，于是得出正解思路。如下。
做这题你需要一定的小学(或初中?)数学知识:
首先区间[l,r]的平均值为(下文设为\bar a)：
\displaystyle \frac{\sum_{i=l}^ra_i}{r-l+1}
方差则是（下文设为s^2):
\displaystyle \frac{\sum_{i=l}^r(a_i-\bar a)^2}{r-l+1}
显然，平均值很好维护，我们只需要维护区间和再在输出时用分数表示区间和除以区间长度就行。
那么我们还要做的其实是用\bar a推出s^2。
我们展开单独的
(a_i- \bar a)^2
=a_i^2-2a_i\bar a+\bar a^2
分别分析a_i^2,2a_i \bar a,和 \bar a^2
我们可以直接单独维护，并不复杂，但对于区间+x的操作我们可以推出懒惰标记的下传公式是:
\sum_{i=l}^r (a_i+x)^2
=\sum_{i=l}^r (a_i^2+2a_ix+x^2)
=\sum_{i=l}^r a_i^2+2x\sum_{i=l}^r a_i+(r-l+1)x^2
在这里我们就很明显看出来我们要维护的就是区间和(\sum a_i)与平方和(\sum a_i^2)了。
但是根据上面式子，我们只需要维护一个懒惰标记。
对于每个区间的平均值我们已经有了维护方法，所以在这我们将其视为定值(\frac{\sum a_i}{r-l+1})，于是我们将式子转换成:
2 \bar a \sum a_i
=\frac{2\sum a_i}{r-l+1} \sum a_i
=\frac{2(\sum a_i)^2}{r-l+1}
显然我们有\sum \bar a^2=[链接登录后可见]\bar a2$
我们再像之前一样代入\bar a
于是乎:
\sum \bar a_i^2
=(r-l+1)(\frac{\sum a_i}{r-l+1})^2
=\frac{(\sum a_i)^2}{r-l+1}
我们发现可以消了，于是列出全式：
s^2=\frac{\sum(a_i-\bar a)^2}{r-l+1}
=\frac{\sum a_i^2-\sum2a_i\bar a+\sum \bar a^2}{r-l+1}
=\frac{\sum a_i^2-\frac{2(\sum a_i)^2}{r-l+1}+\frac{(\sum a_i)^2}{r-l+1}}{r-l+1}
=\frac{(r-l+1)\sum a_i^2-{(\sum a_i)^2}}{(r-l+1)^2}
可能略显麻烦，但是有结果就是好的。
所以我们得出了一个只需要\sum a_i^2和\sum a_i就可以维护区间方差的式子。
求方差时，最后结果就先查询区间和区间平方和，然后按照这个公式输出就可以了。
有几个易错点在这里说一下。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define N 100005
#define ll long long
using namespace std;
struct Rey
{
int l,r;
ll s1,s2;
ll lazadd;
}T[N<<2];
int n,m;
ll a[N];
ll gcd(ll a,ll b)
{
return !b?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return (a*b)/gcd(a,b);
}
int LS(int p){return p<<1;}
int RS(int p){return p<<1|1;}
void UPDATE_sum(int p)
{
T[p].s1=T[LS(p)].s1+T[RS(p)].s1;
T[p].s2=T[LS(p)].s2+T[RS(p)].s2;
}
void build(int p,int l,int r)
{
T[p].l=l,T[p].r=r;
if(l==r){T[p].s1=a[l],T[p].s2=a[l]*a[l];return;}
int mid=(l+r)>>1;
build(LS(p),l,mid);
build(RS(p),mid+1,r);
UPDATE_sum(p);
}
void PD(int p)
{
int L,R;
ll ADD=T[p].lazadd;
L=LS(p),R=RS(p);
T[L].s2+=2*ADD*T[L].s1+(T[L].r-T[L].l+1)*ADD*ADD*1ll;
T[R].s2+=2*ADD*T[R].s1+(T[R].r-T[R].l+1)*ADD*ADD*1ll;
T[L].s1+=ADD*(T[L].r-T[L].l+1)*1ll;
T[R].s1+=ADD*(T[R].r-T[R].l+1)*1ll;
T[L].lazadd+=ADD;
T[R].lazadd+=ADD;
T[p].lazadd=0;
}
void FIX(int p,int l,int r,ll x)
{
if(l>T[p].r||T[p].l>r)return;
if(T[p].l>=l&&T[p].r<=r)
{
T[p].lazadd+=x;
T[p].s2+=T[p].s1*2*x+(T[p].r-T[p].l+1)*x*x*1ll;
T[p].s1+=x*(T[p].r-T[p].l+1)*1ll;
return ;
}
if(T[p].lazadd)PD(p);
FIX(LS(p),l,r,x);
FIX(RS(p),l,r,x);
UPDATE_sum(p);
}
ll Vuq1(int p,int l,int r)//查询区间和
{
ll res=0;
if(l>T[p].r||T[p].l>r)return 0;
if(T[p].l>=l&&T[p].r<=r)return T[p].s1;
if(T[p].lazadd)PD(p);
res+=Vuq1(LS(p),l,r);
res+=Vuq1(RS(p),l,r);
return res;
}
ll Vuq2(int p,int l,int r)//区间平方和
{
ll res=0;
if(l>T[p].r||T[p].l>r)return 0;
if(T[p].l>=l&&T[p].r<=r)return T[p].s2;
if(T[p].lazadd)PD(p);
res+=Vuq2(LS(p),l,r);
res+=Vuq2(RS(p),l,r);
return res;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,1,n);
while(m--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x,y;
ll z;
scanf("%d %d %lld",&x,&y,&z);
FIX(1,x,y,z);
}
if(op==2)
{
int x,y;
scanf("%d %d",&x,&y);
ll sum=Vuq1(1,x,y);
ll mu=y-x+1;
ll G=gcd(sum,mu);
printf("%lld/%lld\n",sum/G,mu/G);
}
if(op==3)
{
int x,y;
scanf("%d %d",&x,&y);
ll sum1=Vuq1(1,x,y);
ll sum2=Vuq2(1,x,y);
ll mu=(ll)(y-x+1);
ll sum=mu*sum2-sum1*sum1*1ll;
mu=mu*mu;
ll G=gcd(sum,mu);
printf("%lld/%lld\n",sum/G,mu/G);
//要求最简形式所以同除以GCD约分
}
}
return 0;
}
