线段树大法好啊！
dingshengyang
·
·
题解
本题解分为 3 部分：
约分方法：分子 $x$、分母 $y$ 同时除以 $\gcd(x,y)$。（不会吧，如果这都不会建议重读小学）。
这里有一个分数结构体，重载了四则运算：
```cpp
typedef pair<LL, LL> PII;
LL gcd(LL a, LL b) {
return (!b) ? (a) : (gcd(b, a % b));
}
struct fra {
LL x, y;
void judge() {//约分
LL gg = gcd(x, y);
x /= gg;
y /= gg;
}
fra operator =(pair<LL, LL> p) {//赋值
x = p.first;
y = p.second;
judge();
return *this;
}
fra operator +(fra p) {//四则运算（自动约分）
LL ny = y * p.y;
LL nx = (p.y * x) + (y * p.x);
fra tmp = {nx, ny};
tmp.judge();
return tmp;
}
fra operator -(fra p) {
LL ny = y * p.y;
LL nx = (p.y * x) - (y * p.x);
fra tmp = {nx, ny};
tmp.judge();
return tmp;
}
fra operator *(fra p) {
LL nx = x * p.x;
LL ny = y * p.y;
fra tmp = {nx, ny};
tmp.judge();
return tmp;
}
fra operator /(fra p) {
fra tmp = {p.y, p.x};
return (*this) * tmp;
}
fra rec() {//倒数
return {y, x};
}
};
```
$2$.公式推导。这题只要有了公式就很简单了。
- 平均数：设总和为 $sum$，区间长度为 $len$，则平均数 $\bar{a}$ 为 $\dfrac{sum}{len}$。
- 方差：方差不好直接推，我们考虑维护平方和。
case $1$：当区间加 $d$ 时，设原来平方和为 $fs$，统一加 $v$，且原来总值为 $sum$。
则现在有：$\sum^{r}_{i=l} (a_i+v)^2$；
用完全平方公式打开得 $\sum^{r}_{i=l} {a_i^2 + a_i \times v \times 2 + v^2}$。
然后得：$\sum^{r}_{i=l} a_i^2 + 2\times v \times \sum^{r}_{i=l} a_i + \sum^{r}_{i=l} v^2$。
我们用 $fs$ 替换 $\sum^{r}_{i=l}$，然后用 $sum$ 替换 $\sum^{r}_{i=l}$。
得现在平方和是：$fs + 2 \times v \times sum + \sum^{r}_{i=l} v^2$。
我们只需要加 $2 \times v \times sum + \sum^{r}_{i=l} v^2$ 就可以了。
---
case $2$：用平方和计算出方差。这个麻烦一点。
原式 $ = \sum^{r}_{i = l} (a_i - \bar{a})^2$。
用完全平方公式打开得 $\sum^{r}_{i = l} a_i^2 - \sum^{r}_{i=l}2 \times \bar{a} \times a_i+ \sum^{r}_{i=l}\bar{a}^2$。
然后得：$fs - \bar{a} \times 2 \times sum + \sum^{r}_{i=l} \bar{a}^2$。
进一步得：$fs - 2 \times sum \times \bar{a} + \dfrac{sum^2}{r-l+1}$。就好算了。
也就是：$fs - 2 \times sum \times \dfrac{sum}{r - l + 1} + \dfrac{sum^2}{r-l+1}$。
得出：$fs - 2 \times \dfrac{sum^2}{r - l + 1} + \dfrac{sum^2}{r-l+1}$。
别急，马上就推好了！
现在有：$fs - \dfrac{2 \times sum^2}{r-l+1} + \dfrac{sum^2}{r-l+1}$。
为了方便我们写程序，还可以化成：$\dfrac{(r-l+1) \times fs - sum^2}{(r-l+1)^2}$。
现在很方便，不是吗？
---
$3$.代码时间！
```cpp
#include <bits/stdc++.h>
#define R register
#define inl inline
#define fastios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define Debug(file) freopen(file".in","r",stdin);freopen(file".out","w",stdout);
using namespace std;
#define L(u) (u << 1)
#define R(u) ((u << 1) | 1)
typedef unsigned long long LL;
LL f(LL x) {
return x * x;
}
typedef pair<LL, LL> PII;
LL gcd(LL a, LL b) {
return (!b) ? (a) : (gcd(b, a % b));
}
struct fra {
LL x, y;
void judge() {
LL gg = gcd(x, y);
x /= gg;
y /= gg;
}
fra operator =(pair<LL, LL> p) {
x = p.first;
y = p.second;
judge();
return *this;
}
fra operator +(fra p) {
LL ny = y * p.y;
LL nx = (p.y * x) + (y * p.x);
fra tmp = {nx, ny};
tmp.judge();
return tmp;
}
fra operator -(fra p) {
LL ny = y * p.y;
LL nx = (p.y * x) - (y * p.x);
fra tmp = {nx, ny};
tmp.judge();
return tmp;
}
fra operator *(fra p) {
LL nx = x * p.x;
LL ny = y * p.y;
fra tmp = {nx, ny};
tmp.judge();
return tmp;
}
fra operator /(fra p) {
fra tmp = {p.y, p.x};
return (*this) * tmp;
}
fra rec() {
return {y, x};
}
};
istream &operator >>(istream &i, fra &f) {
scanf("%llu/%llu", &f.x, &f.y);
return i;
}
ostream &operator <<(ostream &o, fra f) {
printf("%llu/%llu", f.x, f.y);
return o;
}
```
```cpp
/*----------FRACTION-----------PART------------*/
const int N = 1e5 + 5;
struct node {
int l, r;
LL ps, sum;
LL add;
} tr[N * 4];
LL n, m, a[N];
void pushup(int u) {
tr[u].ps = tr[u << 1].ps + tr[u << 1 | 1].ps;
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
node &l = tr[u << 1];
node &r = tr[u << 1 | 1];
node &now = tr[u];
l.add += now.add;
r.add += now.add;
l.ps += (f(now.add) * (l.r - l.l + 1)) + (2ll * l.sum * now.add);
r.ps += (f(now.add) * (r.r - r.l + 1)) + (2ll * r.sum * now.add);
l.sum += (l.r - l.l + 1ll) * now.add;
r.sum += (r.r - r.l + 1ll) * now.add;
now.add = 0;
}
void build(int u, int l, int r) {
if (l == r)
tr[u] = {l, r, f(a[l]), a[l],0};
else {
int mid = l + r >> 1;
tr[u] = {l, r, 0, 0, 0};
build(L(u), l, mid);
build(R(u), mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, LL v) {
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].add += v;
tr[u].ps += (f(v) * (tr[u].r - tr[u].l + 1)) + (2ll * tr[u].sum * v);
tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if (l <= mid) {
modify(u << 1, l, r, v);
}
if (r > mid) {
modify(u << 1 | 1, l, r, v);
}
pushup(u);
}
}
LL query_sum(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u].sum;
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL ans = 0;
if (l <= mid)
ans = query_sum(u << 1, l, r);
if (r > mid)
ans += query_sum(u << 1 | 1, l, r);
return ans;
}
}
LL query_fs(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u].ps;
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL ans = 0;
if (l <= mid)
ans += query_fs(u << 1, l, r);
if (r > mid)
ans += query_fs(u << 1 | 1, l, r);
return ans;
}
}
```
```cpp
/*----------SEGMENT----TREE----PART------------*/
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%llu", &a[i]);
build(1,1,n);
for (int i = 0; i < m; i ++) {
int op, l, r;LL d;
scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
scanf("%llu", &d);
modify(1, l, r, d);
}
if (op == 2) {
fra tmp = {query_sum(1, l, r), (r - l + 1)};
tmp.judge();
cout << tmp << endl;
}
if (op == 3) {
LL sum = query_sum(1,l,r);
LL pfs = query_fs(1,l,r);
LL len = r-l+1;
//printf("pfs:%llu sum:%llu\n",pfs,sum);
fra ans = {len*pfs-sum*sum,len*len};
ans.judge();
cout << ans << endl;
}
}
return 0;
}
```