题面
【题目描述】
还记得 NOIP 2012 提高组 Day2 中的借教室吗？时光飞逝，光阴荏苒，两年过去了，曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。
在接受借教室请求的 n 天中，第 i 天剩余的教室为 ai 个。作为大学借教室服务的负责人，你需要完成如下三种操作共 m 次:
• 第 l 天到第 r 天，每天被归还 d 个教室
• 询问第 l 天到第 r 天教室个数的平均数
• 询问第 l 天到第 r 天教室个数的方差
【输入格式】
第一行包括两个正整数 n 和 m，其中 n 为借教室的天数，m 为操作次数。
接下来一行，共包含 n 个整数，第 i 个整数表示第i 天剩余教室数目为 ai 个。
接下来 m 行，每行的第一个整数为操作编号(只能为 1 或 2 或 3)，接下来包含两个正整数 l 和 r，若操作编号为 1，则接下来再包含一个正整数 d。
【输出格式】
对于每个操作 2 和操作 3，输出一个既约分数(分子与分母互质)表示询问的答案。若答案为 0，请输出“0/1”（不含引号）。
【样例说明】
初始情况下，剩余教室数量为(1, 2, 3, 4, 5)。
第1 次操作为第1 天到第2 天归还3 个教室, 变为(4, 5, 3, 4, 5)。
第2 次操作询问第2 天到第4 天的平均数为(5+3+4)/3 = 4/1。
第3 次操作询问第2 天到第4 天的方差为(1+1+0)/3 = 2/3。
第4 次操作询问第1 天到第5 天的方差为(0.04 + 0.64 +1.44 + 0.04 + 0.64)/5 = 14/25。
$n,m ≤ 10^5$
保证分子的范围不超过64 位带符号整数。
题解
同时也可以是洛谷P1471和P5142的题解
（蒟蒻第一篇破千字的题解）
对于我来说，这题实在是太c了。
首先，区间修改可以让我们很容易地想到线段树。然后，区间求平均就迎刃而解了，因为平均数就是区间和除以区间长度，而区间和正是线段树所维护的。
难点是区间方差。
有一句话说得好：解题时，要回到定义中去。（《怎样解题》）
那么，让我们来看看方差的定义:（ $\overline{x}$ 为区间平均数）
$S^2=\frac{1}{n}[(x_{1}-\overline{x})^2+(x_{2}-\overline{x})^2+\cdots+(x_{n}-\overline{x})^2]=\frac{1}{n}\sum\limits_{i=1}^{n} (x_{i}-\overline{x})^2$
用完全平方公式展开上式，得到：
$S^2=\frac{1}{n}(\sum\limits_{i=1}^{n} x_{i}^2+\sum\limits_{i=1}^{n} 2x_{i}\overline{x}+n*\overline{x}^2)$
很显然，括号中的后两项 $\sum\limits_{i=1}^{n} 2x_{i}\overline{x}$ 和 $n\overline{x}^2$ 都只需要维护区间和就可以算出，但第一项 $\sum\limits_{i=1}^{n} x_{i}^2$ 不可以。观察这个式子就能发现——这不就是区间平方和吗！是的，这也可以使用线段树维护。
接下来，知道怎么维护区间平方和的可以直接看代码，不知道的（比如在写这道题之前的我）建议看看下面这段：
我们发现，当区间 $[$ $l,r$ $]$ 被加上 $d$ 后，区间平方和会这么改变：
由 $\sum\limits_{i=l}^{r} x_{i}^2$ 变为 $\sum\limits_{i=l}^{r} (x_{i}+d)^2$ ，将后式展开，变为：
$\sum\limits_{i=l}^{r} x_{i}^2+\sum\limits_{i=l}^{r} 2x_{i}d+(r-l+1)d^2$
定睛一看：这不解决了吗！第一项就是原来的那个，第二项是我们维护的区间和乘以常数，第三项就是常数！
所以，我们只需要更改一下线段树的更新 $(update)$ 函数和下推 $(pushdown)$ 函数，就可以让线段树维护平方和了:
//pushdown函数中：
s[lson].sqsum+=2*s[p].lazy_tag*s[lson].sum+(s[lson].r-s[lson].l+1)*s[p].lazy_tag*s[p].lazy_tag;
//lson表示左孩子，rson表示右孩子；sum是维护的区间和
s[rson].sqsum+=2*s[p].lazy_tag*s[lson].sum+(s[lson].r-s[lson].l+1)*s[p].lazy_tag*s[p].lazy_tag;
我们也不需要重新写一棵线段树（当然你再写一棵线段树也没问题），只需要在原线段树的结构体里面加一个表示平方和的参数 $(sqsum)$ 就可以了。具体见代码。
剩下的就是这道题奇葩的输出了。把区间和/区间方差等于0的先特判一下，若不等于0，则用辗转相除法求出它与区间长度的最大公约数 $(gcd)$ ，然后把两数都除以 $gcd$ 后输出。
好了，该说的都说完了，上代码！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//不开long long见祖宗
#define lson (p*2)
#define rson (p*2+1)
const int N=1e5+5;
ll n,m,a[N];
inline ll read()//快读函数，可以快速读取（输入）
{
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*w;
}
struct seg{
ll l;
ll r;
ll sum,sqsum;
ll lazy_tag;
}s[N<<2];
inline ll &S(int p)
{
return s[p].sum;
}
inline ll &SQ(int p)
{
return s[p].sqsum;
}
inline ll &R(int p)
{
return s[p].r;
}
inline ll &L(int p)
{
return s[p].l;
}
void push_up(int p)
{
S(p)=S(lson)+S(rson);
SQ(p)=SQ(lson)+SQ(rson);
}
void push_down(int p)
{
if(s[p].lazy_tag)
{
SQ(lson)+=2*s[p].lazy_tag*S(lson)+(R(lson)-L(lson)+1)*s[p].lazy_tag*s[p].lazy_tag;
S(lson)+=(R(lson)-L(lson)+1)*s[p].lazy_tag;
s[lson].lazy_tag+=s[p].lazy_tag;
SQ(rson)+=2*s[p].lazy_tag*S(rson)+(R(rson)-L(rson)+1)*s[p].lazy_tag*s[p].lazy_tag;
S(rson)+=(R(rson)-L(rson)+1)*s[p].lazy_tag;
s[rson].lazy_tag+=s[p].lazy_tag;
s[p].lazy_tag=0;
}
}
void build(int p,int l,int r)
{
if(l==r)
{
s[p]=(seg){l, r, a[l], a[l]*a[l], 0};
return;
}
int mid=(l+r)/2;
build(lson, l, mid);
build(rson, mid+1, r);
L(p)=l;
R(p)=r;
push_up(p);
}
void update(int p, int l, int r, int d)
{
if(l<=L(p)&&R(p)<=r)
{
SQ(p)+=2*d*S(p)+(R(p)-L(p)+1)*d*d;
S(p)+=(R(p)-L(p)+1)*d;
s[p].lazy_tag+=d;
return;
}
push_down(p);
int mid=(R(p)+L(p))/2;
if(l<=mid) update(lson, l, r, d);
if(r>mid) update(rson, l, r, d);
push_up(p);
}
ll query(int p,int l,int r)
{
if(l<=L(p)&&R(p)<=r)
{
return S(p);
}
ll res=0;
push_down(p);
int mid=(R(p)+L(p))/2;
if(l<=mid) res+=query(lson, l, r);
if(r>mid) res+=query(rson, l, r);
return res;
}
ll upquery(int p,int l,int r)
{
if(l<=L(p)&&R(p)<=r)
{
return SQ(p);
}
ll res=0;
push_down(p);
int mid=(R(p)+L(p))/2;
if(l<=mid) res+=upquery(lson, l, r);
if(r>mid) res+=upquery(rson, l, r);
return res;
}
ll gcd(ll a,ll b)
{
while(a%b)
{
ll r=a%b;
a=b;
b=r;
}
return b;
}
void printave(ll l,ll r)
{
ll a=query(1,l,r);
ll b=r-l+1;
if(a==0) printf("0/1\n");
else
{
if(a<0)
{
printf("-");
a=-a;
}
ll d=gcd(a,b);
a/=d;
b/=d;
printf("%lld/%lld\n",a,b);
}
}
void printfc(ll l,ll r)
{
ll t=query(1,l,r);
ll a=(r-l+1)*upquery(1,l,r)-t*t;
ll b=(r-l+1)*(r-l+1);
if(a==0) printf("0/1\n");
else
{
if(a<0)
{
printf("-");
a=-a;
}
ll d=gcd(a,b);
a/=d;
b/=d;
printf("%lld/%lld\n",a,b);
}
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
build(1,1,n);
while(m--)
{
ll op;
op=read();
if(op==1)
{
ll l,r,val;
l=read();
r=read();
val=read();
update(1,l,r,val);
}
else if(op==2)
{
ll l,r;
l=read();
r=read();
printave(l,r);
}
else
{
ll l,r;
l=read();
r=read();
printfc(l,r);
}
}
}
这道题实在是太c了。